[数据结构与算法]LeetCode允许重复选择元素的组合

剑指 Offer II 081. 允许重复选择元素的组合

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

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

来源：LeetCode

使用回溯法。
对于数组中的每个元素都有两个选择，选或者不选，由此可以得到如下的树。

定义一个索引，用来记录已经索引到candidate中的哪个元素，索引idx取值从0到4（candidate的大小，每决定一个元素）；
定义一个集合combine，存放有可能构成target的元素，而最后的ans就是由多个combine数组集合构成的集合；
定义ans集合，存放最终的结果，也就是题目里面要求返回的集合。

在dfs方法中，只有当target=0也就是找到了相应的元素时以及索引的值等于candidate的长度的时候，说明数组里面的元素都被判断过一遍了，也就是说已经走到了叶子节点。

接着就直接跳过idx这个节点，一直往下进行判断，如果碰到返回的情况就是回溯，就会重新判断上一个节点，依次类推。

当遇到需要考虑当前节点的情况的时候，将节点加入combine集合，target值发生变化，同时要接着往下进行考虑。由于每个元素被加入的次数可以不止一次，所以在往下进行搜索时可以再考虑该元素是否可以加入，所以dfs中应该还是idx，而不是idx+1。而且当返回到该节点时，就说明该回溯到上一级的节点，而对应的combine集合的对应添加的元素就应该删除。

以下代码中：res代表ans，cur代表combine，x代表idx

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> cur = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(candidates,0,res,target,cur);
        return res;
    }
    public void dfs(int[] candidates,int x,List<List<Integer>> res,int target,List<Integer> cur){
        if(x==candidates.length){
            return;
        }
        if(target==0){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        dfs(candidates,x+1,res,target,cur);
        if(target>=candidates[x]){
            cur.add(candidates[x]);
            target-=candidates[x];
            dfs(candidates,x,res,target,cur);
            cur.remove(cur.size()-1);
        }
    }
}

参考：官方题解

需要注意：
1.回溯的条件两个：得到target值；数组中元素已经遍历一遍。
2.直接跳过该节点，到达叶节点，然后一步一步的回溯。
3.需要考虑某个节点的时候，注意要将该节点加入cur集合，当回溯时，说明不考虑该节点，要将该节点从cur集合中删除。

这就是算法课老师之前讲的回溯法，过程有点杂，得慢慢理清楚，有了图就容易理解了。

刷题真的太煎熬了。。。