【Day 80 】2021-11-28 - 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

[yanglr]

思路:

列出所有的结果，经常需要用到回溯。

方法: 回溯(dfs)

代码:

实现语言: C++

class Solution {
    vector<vector<int>> res;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> curGroup;
        dfs(candidates, target, curGroup, 0, 0);
        return res;
    }
    void dfs(vector<int>& candidates, int target, vector<int>& curGroup, int sum, int startPos)
    {
        if (sum > target)
            return;
        if (sum == target)
            res.push_back(curGroup);
        else
        {
            int curSum = sum;
            for (int i = startPos; i < candidates.size(); i++)
            {
                sum = curSum;                // 保证sum不受同层元素的影响
                sum = sum + candidates[i];
                curGroup.push_back(candidates[i]);
                dfs(candidates, target, curGroup, sum, i);
                curGroup.pop_back();
            }
        }
    }
};

复杂度分析:

• 时间复杂度: O(2^n)
• 空间复杂度: O(n)

[for123s]

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<vector<int>> res;

    void dfs(vector<int>& temp, int target, vector<int>& candidates, int idx)
    {
        if(target==0)
            res.push_back(temp);
        else if(target>0)
        {
            for(int i=idx;i<candidates.size();i++)
            {
                temp.push_back(candidates[i]);
                dfs(temp,target-candidates[i],candidates,i);
                temp.pop_back();
            }
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        if(target<candidates[0])
            return {};
        vector<int> temp;
        dfs(temp, target, candidates,0);
        return res;
    }
};

[BlueRui]

Problem 39. Combination Sum

Algorithm

• This problem can be solved with backtracking.
• The key here is to select the next number in order so we don't need to deal with results of numbers of different sequence.

Complexity

• Time Complexity: O(N^T/M+1), where N is the number of candidates and T is the target value and M is the minimal value among the candidates.
• Space Complexity: O(T/M).

Code

Language: Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();
    LinkedList<Integer> comb = new LinkedList<>();
    this.backtrack(target, comb, 0, candidates, results);
    return results;
}

private void backtrack(int remain, LinkedList<Integer> comb, int start, int[] candidates, List<List<Integer>> results) {
    if (remain == 0) {
        results.add(new ArrayList<Integer>(comb));
        return;
    } else if (remain < 0) {
        return;
    }
    for (int i = start; i < candidates.length; ++i) {
        comb.add(candidates[i]);
        this.backtrack(remain - candidates[i], comb, i, candidates, results);
        comb.removeLast();
    }
}

[chakochako]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        def dfs(candidates, begin, size, path, res, target):
            if target == 0:
                res.append(path)
                return

            for index in range(begin, size):
                residue = target - candidates[index]
                if residue < 0:
                    break

                dfs(candidates, index, size, path + [candidates[index]], res, residue)

        size = len(candidates)
        if size == 0:
            return []
        candidates.sort()
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)
        return res

[pophy]

思路

• DFS
• 如果target < 0 提前结束剪枝
• 为了避免重复，只能从[index ~ n）之间选择下一个数
  • 比如 2, 2, 3 和 3, 2, 2是一样的，所以当选择3之后就不能再重新选择2， 只能往后看

Java Code

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList();
        dfs(candidates, target, new ArrayList(), 0);
        return res;
    }
    
    private void dfs(int[] candidates, int target, List<Integer> path, int index) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            List<Integer> temp = new ArrayList(path);
            res.add(temp);
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(candidates, target - candidates[i], path, i);
            path.remove(path.size() - 1);
        }                
    }    
}

时间&空间

• 时间 O(2^n)
• 空间 O(n)

[ZacheryCao]

Idea

Backtracking. For each element we have two choices, include it in current list or not. For each choice, we need to remember the remainder we have. Then do the choice again for the candidates starting with current element with current remainder. If eventually the remainder is zero, we find one of the answers. The problem will create an N-ary tree, whose max height is T/M, where T is the target, M is the minimum value from the candidates. Thus the total nodes of the tree will be N^(T/M+1)

Code

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(i, cur, remainder):
            if i>= len(candidates) or remainder < 0:
                return
            if remainder == 0:
                ans.append(cur)
                return
            backtracking(i, cur+[candidates[i]], remainder-candidates[i])
            backtracking(i+1, cur, remainder)
        
        
        ans = []
        backtracking(0, [], target)
        return ans

Complexity

Time: O(N^(T/M+1))
Space: O(T/M)

[Shinnost]

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;
    }
};

[zhangzz2015]

思路

• 排列组合问题，使用回溯，回溯关键画出递归树，另外是否要去重复等条件，因为可以重复选，把当前的index传入下一级，还可选择。时间复杂度为O(n^k) k为树的深度，因为所有的数都是正数，因此当累加的sum > target，已经不需要继续，直接返回，此处有剪枝效果。空间复杂度为O(k)，k为树的深度，最差为O(N)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<int> onePath; 
        vector<vector<int>> ret; 
        int sum =0; 
        
        backTrac(candidates, target, sum, 0, onePath, ret); 
        
        return ret; 
        
    }
    
    void backTrac(vector<int>& candidate, int target, int sum, int start, vector<int>& onePath, vector<vector<int>>& ret)
    {
        if(sum == target)
        {
            ret.push_back(onePath); 
            return; 
        }
        if(sum > target)
            return; 
        if(start>=candidate.size())
            return; 
        
        for(int i=start; i< candidate.size(); i++)
        {
            sum += candidate[i]; 
            onePath.push_back(candidate[i]); 
            backTrac(candidate, target, sum, i, onePath, ret); 
            onePath.pop_back(); 
            sum -= candidate[i]; 
        } 
    }
};

[biancaone]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if candidates is None:
            return []
        result = []
        candidates.sort()
        self.dfs(candidates, result, [], target, 0)
        return result
    
    def dfs(self, candidates, result, sub, target, index):
        if target == 0:
            result.append(list(sub))
            return

        for i in range(index, len(candidates)):
            if candidates[i] > target:
                break
            sub.append(candidates[i])
            self.dfs(candidates, result, sub, target - candidates[i], i)
            sub.pop()

[yachtcoder]

Backtracking.

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        N = len(nums)
        nums.sort()
        ret = []
        def dfs(idx, sum, path):
            if idx == N: return
            if sum > target: return
            if sum == target:
                nonlocal ret
                ret.append(list(path))
                return
            dfs(idx+1, sum, path)
            path.append(nums[idx])
            dfs(idx, sum+nums[idx], path)
            path.pop()
        dfs(0, 0, [])
        return ret

[leungogogo]

• Java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), res, 0);
        return res;
    }
    
    private void dfs(int nums[], int target, int idx, List<Integer> build, List<List<Integer>> res, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(build));
            return;
        } else if (idx == nums.length) {
            return;
        }
        
        for (int i = 0; sum + i * nums[idx] <= target; ++i) {
            for (int j = 0; j < i; ++j) {
                build.add(nums[idx]);
            }
            dfs(nums, target, idx + 1, build, res, sum + i * nums[idx]);
            for (int j = 0; j < i; ++j) {
                build.remove(build.size() - 1);
            }
        }
    }
}

[JiangyanLiNEU]

var combinationSum = function(candidates, target) {
    let res = [];
    const l = candidates.length;
    var dfs = (cur_sum, cur_items, index) => {
        if (cur_sum == target){
            let newIn = [];
            for (let item of cur_items){newIn.push(item)};
            res.push(newIn);
        }else if (cur_sum < target){
            for (let j=index; j<l; j++){
                cur_items.push(candidates[j]);
                dfs(cur_sum+candidates[j], cur_items, j);
                cur_items.pop();
            };
        };
    };
    for (let i=0; i<l; i++){
        dfs(candidates[i], [candidates[i]], i);
    };
    return res;
};

class Solution(object):
    def combinationSum(self, candidates, target):
        length = len(candidates)
        result = []
        def dfs(cur_sum, index, cur_items):
            if cur_sum == target:
                result.append(deepcopy(cur_items))
            if cur_sum > target:
                return
            else:
                for i in range(index, length):
                    dfs(cur_sum+candidates[i], i, cur_items+[candidates[i]])
                    
        for i in range(length):
            dfs(candidates[i], i, [candidates[i]])
        return result