【Day 80 】2023-01-19 - 39 组合总和

[azl397985856]

39 组合总和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/combination-sum/

前置知识

• 剪枝
• 回溯

  题目描述

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

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1：

输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ] 示例 2：

输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

提示：

1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500

[mayloveless]

思路

回溯模块代码，因为可以任意顺序，所以换顺序是重复解，需要不能重复拿值

代码

var combinationSum = function(candidates, target) {
    const res = [];
    var combineFunc = function(count, path) {
        const sum = _.sum(path);
        if (sum > target) return;
        if (sum === target) {
            res.push([...path]);
            return;
        }
        // count 记录位置，不重复选之前的值
        for (let i = count;i<candidates.length;i++) {
            path.push(candidates[i]);
            combineFunc(i,[...path])// 当前的值可多次使用
            path.pop();
        }
    }

    combineFunc(0, []);

    return res;
};

复杂度

时间： 空间：O(target) 调用栈

[Ryanbaiyansong]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # distince integer
        # target
        # 完全背包

        res = []
        n = len(candidates)
        def dfs(i: int, path: List[int], curSum: int) -> None:
            if i == n:
                if curSum == target:
                    res.append(path[:])
                return 

            if curSum > target:
                return 
            path.append(candidates[i])
            dfs(i, path, curSum + candidates[i])
            path.pop()
            dfs(i + 1, path, curSum)
            # path.pop()

        dfs(0, [], 0)
        return res

[tiandao043]

思路

回溯，先排序

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> index;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target,int ii=0) {
        sort(candidates.begin(),candidates.end());
        // combinationSum(candidates,target,0);
        if(target==0){
            ans.push_back(index);            
            return {};
        }
        if(target<candidates[ii]){           
            return {};
        }
        for(int i=ii;i<candidates.size();i++){
            if(target<candidates[i]){break;}
            index.push_back(candidates[i]);
            combinationSum(candidates,target-candidates[i],i);
            index.pop_back();
        }
        return ans;
    }
};

O(S)，其中 S 为所有可行解的长度之和。 O(target)

[snmyj]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        temp = []
        def backtrack(target,sum,startindex):

            if sum > target:
                return
            if sum == target:
                res.append(temp[:])
            for i in range(startindex,len(candidates)):
                sum += candidates[i]
                temp.append(candidates[i])
                backtrack(target,sum,i)
                sum -= candidates[i]
                temp.pop()
        backtrack(target,0,0)
        return

[RestlessBreeze]

code

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }

        dfs(candidates, target, ans, combine, idx + 1);
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};

[klspta]

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

    private void process(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int idx){
        if(idx == candidates.length){
            return;
        }
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        process(res, path, candidates, target, idx + 1);
        path.add(candidates[idx]);
        process(res, path, candidates, target - candidates[idx], idx);
        path.remove(path.size() - 1);
    }
}

[bookyue]

code

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return dfs(candidates, 0, target, new ArrayDeque<>(), new ArrayList<>());
    }

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

        for (int i = idx; i < candidates.length; i++) {
            if (target < candidates[i]) break;

            path.addFirst(candidates[i]);
            dfs(candidates, i, target - candidates[i], path, res);
            path.removeFirst();
        }

        return res;
    }

[FlipN9]

/**
    dfs + backtrack

    TC: O(S)    S为所有可行解的长度之和
                时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和

    SC: O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层
*/
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, new ArrayList<>(), candidates, target);
        return res;
    }

    private void dfs(int idx, List<Integer> combination, int[] candidates, int target) {
        if (idx == candidates.length)
            return;
        if (target == 0) {
            res.add(new ArrayList<>(combination));
            return;
        }
        // 直接跳过
        dfs(idx + 1, combination, candidates, target);
        // 进行选择
        if (target >= candidates[idx]) { // ** 注意: 这里应该是 >=
            combination.add(candidates[idx]);
            // ** 注意: 由于我们可以重复选择 某一个数, idx 在这里不可以 + 1
            dfs(idx, combination, candidates, target - candidates[idx]);
            combination.remove(combination.size() - 1);
        }
    }
}

[Abby-xu]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ret = [] self.dfs(candidates, target, [], ret) return ret

def dfs(self, nums, target, path, ret):
    if target < 0:
        return 
    if target == 0:
        ret.append(path)
        return 
    for i in range(len(nums)):
        self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)

[paopaohua]

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

    private void process(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int idx){
        if(idx == candidates.length){
            return;
        }
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        process(res, path, candidates, target, idx + 1);
        path.add(candidates[idx]);
        process(res, path, candidates, target - candidates[idx], idx);
        path.remove(path.size() - 1);
    }
}

[Jetery]

class Solution {
    Set<List<Integer>> ans = new HashSet<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int n = candidates.length;
        dfs(candidates,target,0,new ArrayList<>());
        List<List<Integer>> res = new ArrayList<>();
        res.addAll(ans);
        return res;
    }
    void dfs(int[] nums,int target,int num,List<Integer> l){
        if (num > target){
            return;
        }
        if (num == target){
            List<Integer> tmp = new ArrayList<>(l);
            Collections.sort(tmp);
            ans.add(tmp);
        }
        int n = nums.length;
        for (int i = 0;i < n;i++){
            l.add(nums[i]);
            dfs(nums,target,num + nums[i],l);
            l.remove(l.size() - 1);
        }
    }
}

[whoam-challenge]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: dp = {i:[] for i in range(target+1)}

    # 这里一定要将candidates降序排列
    for i in sorted(candidates,reverse=True):
        for j in range(i,target+1):
            if j==i:
                dp[j] = [[i]]
            else:
                dp[j].extend([x+[i] for x in dp[j-i]])
    return dp[target]

[Elsa-zhang]

# 39 组合总和
''' 给定一个无重复元素的数组 candidates 和一个目标数 target, 找出 candidates 中所有可以使数字和为 target 的组合
    candidates 中的数字可以 无限制重复被选取
    回溯
'''

class Solution:
    def combinationSum(self, candidates: list[int], target: int):
        def backtrack(ans, templist, candidate, remain, start):

            if remain == 0:
                # return ans.append(templist)
                return ans.append(templist.copy())
            if remain<0:
                return

            for i in range(start, len(candidate)):
                templist.append(candidate[i])
                backtrack(ans, templist, candidate, remain-candidate[i], i)
                templist.pop()

        ans = []
        backtrack(ans, [], candidates, target, 0)

        return ans