58.组合总和

LCR 081. 组合总和

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

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

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

示例 1：

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

示例 2：

输入: candidates = [2], target = 1
输出: []

方法来源：灵茶山艾府

用 dfs(i,target) 来回溯，设当前枚举到 candidates[i]，剩余要选的元素之和为 left，按照选或不选分类讨论：

不选：递归到 dfs(i+1,target)。
选：递归到 dfs(i,target−candidates[i])。注意 i 不变，表示在下次递归中可以继续选 candidates[i]。
注：这个思路类似 完全背包。

如果递归中发现 target=0 则说明找到了一个合法组合，复制一份 path 加入答案。

递归边界：如果 i=n 或者 left<0 则返回。

递归入口：dfs(0,target)。

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

    private void dfs(int i, int target, List<List<Integer>> ans, List<Integer> path , int[] candidates){
        if(target == 0){
            ans.add(new ArrayList(path));
            return ;
        }

        if(i==candidates.length || target<0) return ;

        // 不选
        dfs(i+1, target, ans, path, candidates);

        // 选
        path.add(candidates[i]);
        // i不+1 表示下一轮dfs仍然可以选i,也就是candidates可以被重复选择
        dfs(i, target-candidates[i], ans, path ,candidates);    
        path.remove(path.size()-1);   // 有回溯，恢复现场
    }
}

【记思路，比前两题简单清晰不少，得注意的一点是 选 i不+1】