一道简单的回溯

题目描述

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

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

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

代码

//常规回溯思路
class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//先排序，确认得到的是最优解
        helper(candidates,0,target);
        return res;
    }
    public void helper(int[] candidates,int start,int target)
    {
        if(target==0)
        {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = start;i<candidates.length;i++)
        {
            if(candidates[i]>target)
            {
                break;//下一个数大于target直接break
            }
            list.add(candidates[i]);
            helper(candidates,i,target-candidates[i]);//加入，进入下一步，从i开始
            list.remove(list.size()-1);//回溯
        }
    }
}