大家好！我是曾续缘😃
今天是《LeetCode 热题 100》系列
发车第 58 天
回溯第 4 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
难度：💖💖

解题方法

这道题目要求给定一个整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。其中，candidates 中的同一个数字可以无限制重复被选取。

这里讲解主要的思路：在 backtrack 方法中，使用递归方式进行搜索，对于当前位置cur的候选数字，如果选的话，可以继续选，递归调用前将当前数字加到tmp数组中，递归调用时cur位置不变，sum加上当前数字，如果不选，我们需要将刚才加到tmp数组的数字去掉，恢复tmp原始的状态，递归调用时cur位置加1，sum不变。

Code

查看代码

java

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

解题方法 ​

Code ​

解题方法

Code