https://leetcode-cn.com/problems/combination-sum/description/

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题目分析：

1. 一看到这道题，就感觉要用递归来做，应该是回溯算法。百度证实无误。
2. 然后自己还没有生写过回溯。想了一会儿，结果不对，和正确解法做了一下比较，修改了一下自己的算法。标答是C++的，在java上需要修改一下，一些特别的地方要处理一下。

直接上代码：

/**
 * 核心算法
 * @param candidates 数组
 * @param target 当前递归子问题需要计算的target
 * @param start 开始查找的index
 * @param result 当前递归的result数组
 * @param ans 最后的答案
 */
private void findOne(int[] candidates, int target, int start, List<Integer> result, List<List<Integer>> ans){
    if (target == 0){
        List<Integer> list = new ArrayList<>(result); //这里需要新开一个数组，否则会一直复用这个对象，导致结果不对
        ans.add(list);
        return;
    }else if(target < candidates[start]){
        return; //不符合的结果，不处理。
    }else{
        for (int i = start; i < candidates.length; i++){
            result.add(candidates[i]);
            findOne(candidates, target - candidates[i], i, result, ans);
            result.remove(result.size() - 1);
            //这里有点像树的遍历，这里就是要一个节点和不要一个节点的分支。然后可以重复使用元素，所以递归子问题，仍然从i开始。
        }
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(candidates); //题目没有说排好序的数组，所以这里要先拍个序
    findOne(candidates, target, 0, new ArrayList<>(), ans);
    return ans;
}