博文中会简要介绍Leetcode P0040题目分析及解题思路。
“Combination Sum II”是一道中等难度的题目,是p0039的变形题,考察的是回溯法,也是深度优先搜索,即DFS。
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.
基本思路就是当现有的和小于target的时候继续向下搜索,直到现有的和等于target,或者全部的可能的选择都会导致和大于target时,结束当前探索,回溯到上一层。
除此之外,为了保证无重复排列需要对原数组进行排序。一般去重或者保证无重复,排序是一个很好的解决手段。由于这次的数组里会有重复的值,就需要主动去重,即如果当前值和上一个值相同,则跳过。
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.dfs(candidates, 0, target, 0, new ArrayList<>());
return this.combinations;
}
private List<List<Integer>> combinations = new ArrayList<>();
private void dfs(int[] candidates, int index, int target, int occupied, List<Integer> sequence) {
if (occupied == target) {
List<Integer> copied = new ArrayList<>(sequence);
this.combinations.add(copied);
return;
}
for (int itr=index; itr<candidates.length; ++itr) {
if (occupied+candidates[itr] > target
|| (itr > index && candidates[itr] == candidates[itr-1]))
continue;
sequence.add(candidates[itr]);
this.dfs(candidates, itr+1, target, occupied+candidates[itr], sequence);
sequence.remove(sequence.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> sequence;
this->dfs(candidates, 0, target, 0, sequence);
return this->combinations;
}
private:
vector<vector<int>> combinations;
void dfs(vector<int>& candidates, int index, int target, int occupied, vector<int>& sequence) {
if (occupied == target) {
vector<int> copied(sequence);
combinations.push_back(copied);
return;
}
for (int itr=index; itr<candidates.size(); ++itr) {
if (occupied+candidates[itr] > target
|| (itr > index && candidates[itr] == candidates[itr-1]))
continue;
sequence.push_back(candidates[itr]);
this->dfs(candidates, itr+1, target, occupied+candidates[itr], sequence);
sequence.pop_back();
}
}
};