https://leetcode.com/problems/combination-sum-iii/description/
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
bt(k, 1, n, {}, res);
return res;
}
void bt(int k, int imin, int s, vector<int> v, vector<vector<int>>& res) {
if(s<0 || k<0) return;
if(k==0 && s==0) {
res.push_back(v);
return;
}
for(int i=imin; i<=9; i++) {
v.push_back(i);
bt(k-1, i+1, s-i, v, res);
v.pop_back();
}
}
Showing posts with label BackTracking. Show all posts
Showing posts with label BackTracking. Show all posts
Wednesday, October 18, 2017
Tuesday, October 17, 2017
698. Partition to K Equal Sum Subsets
bool canPartitionKSubsets(vector<int>& nums, int k) {
int N = nums.size();
int sm = 0;
for(int n : nums) sm+=n;
if(sm%k != 0) return false;
int ave = sm/k;
vector<bool> used(N, false);
sort(nums.begin(), nums.end(), greater<int>());
if(nums[0]>ave) return false;
return bt(nums, used, ave, ave, k);
}
bool bt(vector<int>&nums, vector<bool>& used, int s, const int ave, int p) {
if(s< 0) return false;
if(p< 0) return false;
if(p==0) return true;
if(s==0) return bt(nums, used, ave, ave, p-1);
for(int i=0; i<nums.size(); i++) {
if(!used[i]) {
//if(nums[i]>ave) return false;
used[i] = true;
bool b = bt(nums, used, s-nums[i], ave, p);
if(b) return true;
used[i] = false;
}
}
return false;
}
int N = nums.size();
int sm = 0;
for(int n : nums) sm+=n;
if(sm%k != 0) return false;
int ave = sm/k;
vector<bool> used(N, false);
sort(nums.begin(), nums.end(), greater<int>());
if(nums[0]>ave) return false;
return bt(nums, used, ave, ave, k);
}
bool bt(vector<int>&nums, vector<bool>& used, int s, const int ave, int p) {
if(s< 0) return false;
if(p< 0) return false;
if(p==0) return true;
if(s==0) return bt(nums, used, ave, ave, p-1);
for(int i=0; i<nums.size(); i++) {
if(!used[i]) {
//if(nums[i]>ave) return false;
used[i] = true;
bool b = bt(nums, used, s-nums[i], ave, p);
if(b) return true;
used[i] = false;
}
}
return false;
}
Thursday, September 28, 2017
526. Beautiful Arrangement
https://leetcode.com/problems/beautiful-arrangement/description/
void count(int N, vector<bool>& fil, int& res) {
if(N==0) {res++; return;}
for(int i=fil.size()-1; i>=0; i--) {
if(!fil[i] && (N%(i+1)==0 || (i+1)%N==0)){
fil[i] = true;
count(N-1, fil, res);
fil[i] = false;
}
}
}
int countArrangement(int N) {
int res = 0;
vector<bool> fil(N, false);
count(N, fil, res);
return res;
}
void count(int N, vector<bool>& fil, int& res) {
if(N==0) {res++; return;}
for(int i=fil.size()-1; i>=0; i--) {
if(!fil[i] && (N%(i+1)==0 || (i+1)%N==0)){
fil[i] = true;
count(N-1, fil, res);
fil[i] = false;
}
}
}
int countArrangement(int N) {
int res = 0;
vector<bool> fil(N, false);
count(N, fil, res);
return res;
}
Subscribe to:
Posts (Atom)