39. Combination Sum

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(candidates, path, res, target, 0);
    return res;
}

public void dfs(int[] candidates, List<Integer> path, List<List<Integer>> res, int target, int pointer) {
    if (target < 0) return;
    else if (target == 0) res.add(new ArrayList<>(path));
    else {
        for (int i = pointer; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(candidates, path, res, target - candidates[i], i); // allow repetitions
            path.remove(path.size() - 1);
        }
    }
}

pointer的作用是，每次path进行递归的时候，从pointer（当前数字的index开始向后循环计数），这是防止重复数组的出现，比如[2, 2, 3], [3, 2, 2]这类的。

注意点：path是会被修改的所以添加的时候要另外创建一个副本。