博文中会简要介绍Leetcode P0039题目分析及解题思路。
“Combination Sum”是一道中等难度的题目，考察的是回溯法，也是深度优先搜索，即DFS。
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
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>> combinationSum(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)
continue;
sequence.add(candidates[itr]);
this.dfs(candidates, itr, target, occupied+candidates[itr], sequence);
sequence.remove(sequence.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> combinationSum(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)
continue;
sequence.push_back(candidates[itr]);
this->dfs(candidates, itr, target, occupied+candidates[itr], sequence);
sequence.pop_back();
}
}
};