组合总和

原题链接

使用的方法

回溯算法

解题思路

• 给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
• 我们可以使用回溯算法来生成所有可能的组合。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过递归地构建组合来生成所有的组合。
• 我们从空集开始，逐步添加数组中的元素来构建组合。在每一步，我们有两个选择：要么包含当前元素，要么不包含当前元素。通过递归地探索这两种选择，我们可以生成所有可能的组合。
• 递归的终止条件是当我们处理到数组的最后一个元素时，我们将当前的组合添加到结果列表中。通过这种方式，我们可以生成所有可能的组合，并最终返回结果列表。

代码实现

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

    public void backtrack(int[] candidates,int target,int start,List<Integer> cur,List<List<Integer>> res){
        if(target == 0){
            res.add(new ArrayList<>(cur));
            return;
        }
        
        for(int i = start;i < candidates.length;i++){
            if(candidates[i] > target) continue;
            cur.add(candidates[i]);
            backtrack(candidates,target - candidates[i],i,cur,res);
            cur.remove(cur.size() -1);
        }
    }
}