### 题目

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

[
[7],
[2, 2, 3]
]


### 暴力递归回溯 $O(n^n)$

[8,7,4,3]，目标值11。先排序，得到[3,4,7,8]。对数组中的每个数，只要加上历史小于目标值就开下一层递归。

0+3 < 11    >>>    [3], 递归面对[3,4,7,8]
0+4 < 11    >>>    [4], 递归面对[3,4,7,8]
0+7 < 11    >>>    [7], 递归面对[3,4,7,8]
0+8 < 11    >>>    [8], 递归面对[3,4,7,8]


#### 代码

public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
recursion(new ArrayList<Integer>(), 0, candidates, target, result);
return result;
}
public void recursion(List<Integer> register, int sum, int[] candidates, int target, List<List<Integer>> result) {
for (int i : candidates) {
if (sum + i > target) { break; } // 剪枝
List<Integer> copy = new ArrayList<>(register);
if (sum + i == target) {
Collections.sort(copy);
if (! result.contains(copy)) {
}
} else {
recursion(copy,sum+i,candidates,target,result);
}
}
}
}


#### 结果

So stupid, but it works.

### 顺序遍历，不重复 $O(2^n)$

[3]，从3开始，肯定有3，可能有4,7,8的所有组合。
[4]，从4开始，没有3，肯定有4，可能有7,8的所有组合。
[7]，从7开始，没有3，4，肯定有7，可能有8的所有组合。
[8]，从8开始，没有3，4，7，只有8的所有组合。


#### 代码

public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
recursion(new ArrayList<Integer>(), 0, candidates, 0, target, result);
return result;
}
public void recursion(List<Integer> register, int sum, int[] candidates, int start, int target, List<List<Integer>> result) {
for (int i = start; i < candidates.length; i++) {
int newSum = sum + candidates[i];
if (newSum > target) { break; }
List<Integer> copy = new ArrayList<>(register);
if (newSum == target) {
} else {
recursion(copy,newSum,candidates,i,target,result);
}
}
}
}


### 尝试用Integer[]替代ArrayList<Integer>提高效率，失败！

#### 代码

public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
recursion(new Integer[0], 0, candidates, 0, target, result);
return result;
}
public void recursion(Integer[] register, int sum, int[] candidates, int start, int target, List<List<Integer>> result) {
for (int i = start; i < candidates.length; i++) {
int newSum = sum + candidates[i];
if (newSum > target) { break; }
Integer[] copy = Arrays.copyOf(register,register.length+1);
copy[copy.length-1] = candidates[i];
if (newSum == target) {
} else {
recursion(copy,newSum,candidates,i,target,result);
}
}
}
}


### 重点来啦：标准的回溯算法 $O(2^n)$

List<Integer> copy = new ArrayList<>(register);


#### 代码

public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(new ArrayList<Integer>(), target, candidates, 0, result);
return result;
}
public void backtrack(List<Integer> temp, int remain, int[] candidates, int start, List<List<Integer>> result) {
if (remain == 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
if (remain < candidates[i]) { break; } // 剪枝。当发现某个数太大，后面的更大的数也不用尝试了。
// 回溯算法的精髓就体现在这三行上