首页 > 代码库 > [LeetCode] Combination Sum II
[LeetCode] Combination Sum II
Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]
Solution:
int differentCandidatesNum;int* differentCandidates;int* differentCandidatesCount;vector<vector<int> > ans;int targ;void dfs(int k, int curSum, vector<int> curCount){ /* cout << "k = " << k << " curSum = " << curSum << endl; cout << "curCount: "; for(int i = 0;i < curCount.size();i++) cout << curCount[i] << " "; cout << endl; */ if(curSum > targ) return; if(curSum == targ) { vector<int> curCom; for(int i = 0;i < curCount.size();i++) for(int j = 0;j < curCount[i];j++) curCom.push_back(differentCandidates[i]); ans.push_back(curCom); return; } if(k >= differentCandidatesNum) return; //try the k the no duplicate candidates //choose 0 to differentCandidatesCount[k]‘s k to check if this is a good combination for(int i = 0;i <= differentCandidatesCount[k];i++) { curCount.push_back(i); dfs(k + 1, curSum + i * differentCandidates[k], curCount); curCount.pop_back(); }}vector<vector<int> > combinationSum2(vector<int> &num, int target) { if(num.size() == 0) return ans; //sort the candidate num for(int i = 0;i < num.size();i++) { bool continueBubble = false; for(int j = 0;j < num.size() - i - 1;j++) { if(num[j] > num[j + 1]) { int tmp = num[j]; num[j] = num[j + 1]; num[j + 1] = tmp; continueBubble = true; } } if(continueBubble == false) break; } //get no duplicate candidates int curNum = num[0], counter = 1; differentCandidates = new int[num.size()]; differentCandidatesCount = new int[num.size()]; differentCandidatesNum = 0; for(int i = 1;i < num.size();i++) { if(curNum == num[i]) { counter++; } else { differentCandidates[differentCandidatesNum] = curNum; differentCandidatesCount[differentCandidatesNum] = counter; differentCandidatesNum++; counter = 1; curNum = num[i]; } } //add last no duplicate candidate differentCandidates[differentCandidatesNum] = curNum; differentCandidatesCount[differentCandidatesNum] = counter; differentCandidatesNum++; // for(int i = 0;i < differentCandidatesNum;i++) // cout << differentCandidates[i] << " num = " << differentCandidatesCount[i] << endl; //begin dfs to search combinations. targ = target; vector<int> cur; dfs(0, 0, cur); delete [] differentCandidates; return ans; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。