LeetCode40. Combination Sum II
文章目录
- 一、题目
- 二、题解
一、题目
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Constraints:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
二、题解
使用used数组进行去重
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<int>& used){if(sum > target) return;if(sum == target){res.push_back(path);return;}for(int i = startIndex;i < candidates.size();i++){if(i > 0 && candidates[i-1] == candidates[i] && used[i-1] == 0)continue;sum += candidates[i];used[i] = 1;path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1,used);sum -= candidates[i];used[i] = 0;path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {int n = candidates.size();vector<int> used(n,0);sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return res;}
};
使用startIndex进行去重
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex){if(sum > target) return;if(sum == target){res.push_back(path);return;}for(int i = startIndex;i < candidates.size() && candidates[i] + sum <= target;i++){if(i > startIndex && candidates[i-1] == candidates[i])continue;sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1);sum -= candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {int n = candidates.size();sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return res;}
};