【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

[yingliucreates]

link:

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

代码 Javascript

function combinationSum(candidates, target) {
  var buffer = [];
  var result = [];
  search(0, target);
  return result;

  function search(startIdx, target) {
    if (target === 0) return result.push(buffer.slice());
    if (target < 0) return;
    if (startIdx === candidates.length) return;
    buffer.push(candidates[startIdx]);
    search(startIdx, target - candidates[startIdx]);
    buffer.pop();
    search(startIdx + 1, target);
  }
}

[q815101630]

回溯

经典回溯问题 需要学习整个回溯的写法，套上模板就可以 确定return 条件即可

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

代码

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

        self.ans = []
        size = len(candidates)

        def backtrack(curSum, start, path):
            if curSum == target:
                self.ans.append(path[:])
                return
            for i in range(start, size):
                if candidates[i]+curSum > target:
                    continue
                if candidates[i] > target:
                    continue

                backtrack(curSum+candidates[i], i, path+[candidates[i]])

        backtrack(0, 0, [])
        return self.ans

[chenming-cao]

解题思路

回溯+剪枝。参考官方题解。因为数字可以无限制重复被选取，所以要用回溯，考虑所有情况。回溯过程中我们可以剪掉sum超过target的情况，如果遇到sum等于target，我们就将现有的符合条件的组合存到结果的List中。为了去重，规定每一个递归树的节点的子节点不能取在candidates数组中出现在该节点之前的元素。

代码

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

    private void backtrack(int pos, int cur, int[] candidates, List<Integer> list, List<List<Integer>> result) {
        // if sum is equal to target, one route is found
        if (cur == 0) {
            result.add(new ArrayList<>(list)); // cannot use list here, need to specify the type (new ArrayList<>())
            return;
        }
        // if sum is greater than target
        if (cur < 0) {
            return;
        }
        // if sum is smaller than target, continue backtracking
        // can only peak elements which showed up at the current index or later to avoid duplication
        for (int i = pos; i < candidates.length; i++) {
            list.add(candidates[i]);
            backtrack(i, cur - candidates[i], candidates, list, result);
            list.remove(list.size() - 1);
        }
    }
}

复杂度分析

• 时间复杂度：O(n^(target/min))，n为candidates数组的长度，min为数组中最小元素，target/min为递归栈的最大深度
• 空间复杂度：O(target/min)，记录路径信息的list的长度不超过target/min

[CoreJa]

思路

这个题目其实就是背包问题的展开式，背包问题一般只要求返回最优解的长度/个数，但这个要求把具体的解展开

因此思路有两个方向，沿用dp和回溯+剪枝

• 沿用dp的话那就需要把dp表格中的局部最优解调整为所有解的展开，也就是dp的每个格子都是一个数组，

  • dp的解法空间开销会比较大，好处是思路很容易想，坏处是速度会比较慢
  • dp的核心在于用已知推未知，dp的答案建立在已有的结果上，所以dp必须把0到target的每个结果都算出来并保存下来
    • 回溯+剪枝的话，回溯本身没什么难点，无非就是
  • dfs每次带入一个target，把所有candidate遍历一遍，递归调用时带入target-candidate[i]
  • 此外为了结果不重复出现(变成了排列问题)，candidate应当不向前遍历(即用了3之后的递归不应再使用前面的2)
  • 剪枝方面可以用搜索顺序剪枝优化
    • 当candidate排序后，如果当前的candidate已经大于当前target，那么这个以及后面的candidate就不需要考虑了 """

      代码

      
      class Solution:
      # 动规解法
      def combinationSum1(self, candidates: List[int], target: int) -> List[List[int]]:
      dp = [[[]]] + [[] for _ in range(target)]
      for i in range(len(candidates)):
      for j in range(candidates[i], target + 1):
          if dp[j - candidates[i]]:
              dp[j] += [tmp + [candidates[i]] for tmp in dp[j - candidates[i]]]
      return dp[-1]

  回溯+剪枝解法(比动规更好)

  def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] candidates.sort()

  def dfs(target, cur_ans, candidates):
      if target == 0:
          ans.append(cur_ans)
          return
      for i, c in enumerate(candidates):
          if c > target:
              break
          dfs(target - c, cur_ans + [c], candidates[i:])
  
  dfs(target, [], candidates)
  return ans

[ginnydyy]

Problem

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

Solution

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return res;
        }

        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        helper(candidates, 0, target, list, res);
        return res;
    }

    private void helper(int[] nums, int start, int remain, List<Integer> list, List<List<Integer>> res){
        if(remain == 0){
            res.add(new ArrayList<>(list));
            return;
        }

        if(remain < 0 || start == nums.length){
            return;
        }

        for(int i = start; i < nums.length; i++){
            if(nums[i] <= remain){
                list.add(nums[i]);
                helper(nums, i, remain - nums[i], list, res);
                list.remove(list.size() - 1);
            }else{
                return;
            }
        }
    }
}

Complexity

• T: O(n * 2^n). n is the length of candidates. It is the worst case. There are 2^n combinations, for each combination, it costs O(n) to make the decision on all n positions. But after pruning, in practise, the actual complexity is much better than it.
• S: It depends on the sorting algorighm. Also, O(target) space is required for storing the temporary result list. In the worst case, the list size is target.

[CoreJa]

思路

这个题目其实就是背包问题的展开式，背包问题一般只要求返回最优解的长度/个数，但这个要求把具体的解展开

因此思路有两个方向，沿用dp和回溯+剪枝

• 沿用dp的话那就需要把dp表格中的局部最优解调整为所有解的展开，也就是dp的每个格子都是一个数组，

  • dp的解法空间开销会比较大，好处是思路很容易想，坏处是速度会比较慢
  • dp的核心在于用已知推未知，dp的答案建立在已有的结果上，所以dp必须把0到target的每个结果都算出来并保存下来
    • 回溯+剪枝的话，回溯本身没什么难点，无非就是
  • dfs每次带入一个target，把所有candidate遍历一遍，递归调用时带入target-candidate[i]
  • 此外为了结果不重复出现(变成了排列问题)，candidate应当不向前遍历(即用了3之后的递归不应再使用前面的2)
  • 剪枝方面可以用搜索顺序剪枝优化
    • 当candidate排序后，如果当前的candidate已经大于当前target，那么这个以及后面的candidate就不需要考虑了 """

      代码

      
      class Solution:
      # 动规解法
      def combinationSum1(self, candidates: List[int], target: int) -> List[List[int]]:
      dp = [[[]]] + [[] for _ in range(target)]
      for i in range(len(candidates)):
      for j in range(candidates[i], target + 1):
          if dp[j - candidates[i]]:
              dp[j] += [tmp + [candidates[i]] for tmp in dp[j - candidates[i]]]
      return dp[-1]

  回溯+剪枝解法(比动规更好)

  def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] candidates.sort()

  def dfs(target, cur_ans, candidates):
      if target == 0:
          ans.append(cur_ans)
          return
      for i, c in enumerate(candidates):
          if c > target:
              break
          dfs(target - c, cur_ans + [c], candidates[i:])
  
  dfs(target, [], candidates)
  return ans

[Daniel-Zheng]

思路

回溯。

代码(C++)

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

    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) res.push_back(path);
        for (int i = startIndex; i < candidates.size(); i++) {
            if (sum + candidates[i] > target) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            path.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)，N为Candidates中所有符合条件解的长度。
• 空间复杂度：O(T)，T为Target大小。

[ai2095]

39. Combination Sum

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

Topics

-Backtracking

思路

Backtracking

代码 Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dp(combination, val_left, indx):
            if val_left == 0:
                res.append(combination[:])
                return

            for i in range(indx, len(candidates)):
                if candidates[i] <= val_left:
                    combination.append(candidates[i])
                    dp(combination, val_left - candidates[i], i)
                    combination.pop()

        candidates.sort()
        res = []
        dp([], target, 0)
        return res

复杂度分析

Let N be the number of candidates, T be the target value, and M be the minimal value among the candidates. 时间复杂度： O(N^(T/M+1))
空间复杂度： O(T/M)

[yan0327]

回溯 + 深度DFS

func combinationSum(candidates []int, target int) [][]int {
    if len(candidates) == 0{
        return nil
    }
        out := [][]int{}
        var dfs func(start int,sum int,path []int)
        dfs = func(start int,sum int,path []int){
            if sum >= target{
                if sum == target{
                    temp := make([]int,len(path))
                    copy(temp,path)
                    out = append(out,temp)
                }
                    return
            }
                for i:=start;i<len(candidates);i++{
                    path = append(path,candidates[i])
                    dfs(i,sum+candidates[i],path)
                    path = path[:len(path)-1]
                }
        }
        dfs(0,0,[]int{})
        return out

}

时间复杂度O(2^n) 空间复杂度O（n）

[kidexp]

thoughts

DFS 回溯所有解 遇到大于target的可以不用进行下去

code

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

        def dfs(index, temp_sum):
            if temp_sum < target:
                for i in range(index, len(candidates)):
                    single_solution.append(candidates[i])
                    dfs(i, temp_sum + candidates[i])
                    single_solution.pop()
            elif temp_sum == target:
                results.append(list(single_solution))

        dfs(0, 0)
        return results

complexity

Time O(2^n) Space O(target)

[chen445]

代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result=[]
        path=[]
        def backtracking(index,current_sum):
            if current_sum == target:
                result.append(path.copy())
                return 
            if current_sum > target:
                return
            for i in range(index,len(candidates)):
                path.append(candidates[i])
                backtracking(i,current_sum+candidates[i])
                path.pop()
        backtracking(0,0) 
        return result

复杂度

Time: (N^(T/M+1)) T is the target, M is the min number

Space: O(n)

[Serena9]

代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(ans,tempList, candidates, remain, start):
            if remain < 0: return
            elif remain == 0: return ans.append(tempList.copy())
            for i in range(start, len(candidates)):
                tempList.append(candidates[i])
                backtrack(ans, tempList, candidates, remain - candidates[i], i)
                tempList.pop()

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

[joeytor]

思路

直接使用回溯方法会有一个问题, 因为没有去重复, 所以 [2,2,3] 和 [3,2,2] 会是不同的回溯组合, 会大大增加时间复杂度, 并且答案也需要再次去重又增加了复杂度

所以希望在搜索的过程中就不要产生重复的元素, 方法是每次搜索的时候限制只能使用元素本身和之后的元素

eg. 元素是 [2,3,4] 在 index = 0 的时候可以使用 [2,3,4], 在 index = 1 的时候只能使用 [3,4] 这样避免了 [3,2,2] 和 [2,2,3] 这样的重复组合出现

每次如果 num == 0 是base case, 代表已经找到了一个符合条件的组合, 那么就添加到 res 水煮鱼中

否则根据上面的分析使用从 index 开始的 candidates (包含 index 本身因为允许每个数字允许使用无数次), 每次如果 num-c ≥ 0, 代表有可能可以使用这个 candidate c, 那么继续 dfs, 使用 c 时从 c 的 index 开始, 因为避免再次使用前面的数字造成重复, 使用前面数字的 case 在前面都已经被 cover 了

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

        def dfs(num, cur, index):
            if num == 0:
                res.append(cur)
                return

            for i,c in enumerate(candidates):
                if i < index:
                    continue
                if num - c >= 0:
                    dfs(num-c, cur+[c],i)

        dfs(target, [], 0)
        return res

复杂度

时间复杂度: O(n^(target/min)) n 为 candidates 的长度, target/min 是递归栈的最大深度, 这是很宽松的上届, 因为可能有的值很大搜索次数就很少, 并且加上剪枝搜索次数会更少

空间复杂度: O(target/min) 递归栈的深度最大是 target/min, 并且 记录 path 上节点的 list 的长度也不大于 target/min

[okbug]

class Solution {
public:

    vector<vector<int>> ans;
    vector<int> path;

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

    void dfs(vector<int>& c, int u, int target) {
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        for (int i = 0; c[u] * i <= target; i ++ ) {
            dfs(c, u + 1, target - c[u] * i);
            path.push_back(c[u]);
        }

        for (int i = 0; c[u] * i <= target; i ++ ) {
            path.pop_back();
        }
    }
};

[wenlong201807]

代码块

var combinationSum = function (candidates, target) {
  const ans = [];
  const dfs = (target, combine, idx) => {
    if (idx == candidates.length) {
      return;
    }

    if (target === 0) {
      ans.push(combine);
      return;
    }

    dfs(target, combine, idx + 1);// 直接跳过

    // 选择当前的数据
    if (target - candidates[idx] >= 0) {
      dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
    }
  }

  dfs(target, [], 0);
  return ans;
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[chun1hao]

var combinationSum = function(candidates, target) {
    const ans = [];
    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        dfs(target, combine, idx + 1);
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    }

    dfs(target, [], 0);
    return ans;
};

[laofuWF]

# backtrack
# time: O(N^(target / min_value))
# space: O(target / min_value)

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

    def backtrack(self, res, nums, curr_list, curr_sum, target):
        if curr_sum == target:
            res.append(curr_list.copy())
            return

        if curr_sum > target:
            return

        for i in range(len(nums)):
            curr_list.append(nums[i])
            self.backtrack(res, nums[i:], curr_list, curr_sum + nums[i], target)
            curr_list.pop()

[vincentLW]

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

[skinnyh]

Note

• Pass along the current index in backtracking. In each recursion, we only pick numbers starting from the current index to avoid duplicate results.
• Complexity analysis: Backtracking is a N-nary tree where N is the length of candidates. The worst case depth is H = target/min(candidates) so the time complexity is O(N^H) and the space complexity is O(H) which is the recursion depth and also the longest path length.

Solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start, target, path):
            if target == 0:
                res.append(path.copy())
                return
            for i in range(start, len(candidates)):
                if candidates[i] <= target:
                    path.append(candidates[i])
                    backtrack(i, target - candidates[i], path)
                    path.pop()
        res = []
        backtrack(0, target, [])
        return res

Time complexity: O(N^H)

Space complexity: O(H)

[akxuan]

用index skip 掉重复的数字

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if len(candidates) <= 0 : return []

        candidates.sort()

        def dfs(target, path, res, candidates, start):
            if target == 0:
                res.append(path.copy())
            else:
                for i in range(start, len(candidates)):
                    left = target- candidates[i]
                    if left < 0: 
                        break

                    path.append(candidates[i])

                    # 比i 小的去除
                    dfs(left, path, res, candidates,i)
                    path.pop()

        res = []

        dfs(target,[], res, candidates, 0)   
        #print(res)
        return res

[tongxw]

思路

回溯，因为数字都是正数，所以可以先排序，如果发现数字已经大于目标了，可以提前退出。

代码

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

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

        for (int i=start; i<nums.length; i++) {
            if (nums[i] > target) {
                break;
            }
            path.add(nums[i]);
            dfs(nums, i, target - nums[i], ans, path);
            path.remove(path.size() - 1);
        }
    }
}

回溯深度 h = target / min(nums) TC: O(n^h) SC: O(h)

[guangsizhongbin]

func combinationSum(candidates []int, target int) (ans [][]int) {
    comb := []int{}
    var dfs func(target, idx int)

    dfs = func(target, idx int){
        // 到达边界时，直接返回
        if idx == len(candidates) {
            return 
        }

        // 如果target 为0 的情况
        if target == 0{
            // 直接返回空
            ans = append(ans, append([]int(nil), comb...))
            return 
        }

        // 不选择当前位置
        dfs(target, idx + 1)

        // 选择当前位置, 
        if target - candidates[idx] >= 0 {
            // 未到达目标时
            comb = append(comb, candidates[idx])
            // dfs 除本点外的点
            dfs(target-candidates[idx], idx)
            comb = comb[:len(comb) - 1]
        }
    }

    // 从下标为0的位置开始
    dfs(target, 0)
    return
}

[learning-go123]

思路

• 回溯

代码

• 语言支持：Go

Go Code:

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var f func(int, int, []int)
    f = func(pos, sum int, nums []int) {
        if sum == target {
            res = append(res, append([]int{}, nums...))
            return
        }
        if sum > target {
            return
        }
        for i:=pos;i<len(candidates);i++ {
            f(i, sum+candidates[i], append(nums, candidates[i]))
        }
    }
    f(0, 0, []int{})
    return res
}

复杂度分析

令 n 为数组长度。

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

[a244629128]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    var res = [];
    candidates.sort((a,b)=>{return a-b});
    var dfs = function(i,candidates,target,recorder){
        //backtrack
        if(target <0){
            return;
        }
        //base
        if(target === 0){
            res.push(recorder.slice());
            return;
        }
        //dfs case
        for(let j=i; j<candidates.length;j++){
            recorder.push(candidates[j]);
            dfs(j,candidates,target-candidates[j],recorder);
            recorder.pop();
        }
    }
    dfs(0,candidates,target,[]);
    return res;
};

[ysy0707]

思路：回溯+剪枝

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

    public void backtrack(List<Integer> path, int[] candidates, int target, int sum, int index){
        //找到了组合
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i < candidates.length; i++){
            if(sum + candidates[i] > target){
                break;
            }
            path.add(candidates[i]);
            //由于每一个元素可以重复使用，下一轮搜索的起点依然是 i
            backtrack(path, candidates, target, sum + candidates[i], i);
            //回溯
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

[carterrr]

class 组合总和_39_重做版 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();

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

    private void dfs(int[] candidates, int target, int sum, int begin) {
        if(sum > target) return;
        if(sum == target) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = begin; i< candidates.length; i++) {

            tmp.add(candidates[i]);
            // i = begin 可以从 begin再次遍历  因此可以一直取begin 向下递归
            dfs(candidates, target, sum + candidates[i], i);
            tmp.remove(tmp.size() -1);
        }
    }
}

[yj9676]

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

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}

[pan-qin]

Idea

backtracking. each num is nums can be chosen or not chosen. If the current num is not chosen, go to the next num. If it is chosen, backingtracking.

Complexity:

Time: O(n*2^n). Space: O(height) height is the recursion depth

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<>();
        dfs(candidates,target,res,combine,0);
        return res;
    }
    public void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> combine, int idx) {
        if(idx==candidates.length)
            return;
        if(target==0) {
            res.add(new ArrayList<Integer>(combine));
            return;
        }
        dfs(candidates,target,res,combine,idx+1);

        if(target-candidates[idx]>=0) {
            combine.add(candidates[idx]);
            dfs(candidates,target-candidates[idx],res,combine,idx);
            combine.remove(combine.size()-1);
        }

    }
}

[thinkfurther]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(ans,tempList, candidates, remain, start):
            if remain < 0: return
            elif remain == 0: return ans.append(tempList.copy()) 
            for i in range(start, len(candidates)):
                tempList.append(candidates[i])
                backtrack(ans, tempList, candidates, remain - candidates[i], i)
                tempList.pop()

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

[user1689]

题目

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

思路

DFS

python3

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

        # time n * 2**n
        # space target
        # 二进制枚举
        def dfs(idx, path, total):
            if total > target:
                return

            if total == target:
                res.append(path[:])
                return

            if idx == len(candidates):
                return 

            # 不选
            dfs(idx + 1, path, total)

            # 选
            if candidates[idx] <= target - total:
                path.append(candidates[idx])
                dfs(idx, path, total + candidates[idx])
                path.pop()

        res = []
        path = []
        dfs(0, path, 0)

        return res

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # time (n+m-1)! / m!(n-1)!
        # space target
        def dfs(startIdx, path, total):
            if total > target:
                return

            if total == target:
                res.append(path)
                return

            for i in range(startIdx, len(candidates)):
                dfs(i, path + [candidates[i]], total + candidates[i])

        res = []
        path = []
        dfs(0, path, 0)

        return res

时间复杂度

• time n * 2**n
• space target

相关题目

1. https://leetcode-cn.com/problems/combination-sum-ii/
2. https://leetcode-cn.com/problems/combination-sum-iii/
3. https://leetcode-cn.com/problems/combination-sum-iv/

[RocJeMaintiendrai]

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0) return res;
        helper(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }

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

复杂度分析

时间复杂度

O(2^n)

空间复杂度

O(n)

[wenjialu]

Thinking process：

1) 223 is the same as 322, 2)repeated is allowed, so, we are going to pick a new number equals or after the number it started when doing the recursion.

Code

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

1) 223 is the same as 322, 2)repeated is allowed, so we are going to pick a new number equals or after the number it started when doing the recursion.

    path, res = [], []

    self.calSum(0, candidates, target, [], res)
    return res  #have to pass the outside variable “res” rather than [] into the function, so that it can be updated.

def calSum(self, idxed, candidates, target, path, res):   
# print(path, res)
    if target < 0:
        return

    if target == 0:
        res.append(path[:]) 
        # print(res) 
        return 

    for idx in range(idxed, len(candidates)): # 去重
        # print("start",idx)
        # print( idx, candidates[idx], target, target - candidates[idx])      
        self.calSum(idx, candidates, target - candidates[idx], path + [candidates[idx]], res) # 这里传的idx就可以追踪这层的起点是啥了。

Complexity

TIme：n^m? (not sure) n:length of candidates m:target. Space： O(target) （not sure）

[ymkymk]

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

public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
    if (idx == candidates.length) {
        return;
    }
    if (target == 0) {
        ans.add(new ArrayList<Integer>(combine));
        return;
    }
    // 直接跳过
    dfs(candidates, target, ans, combine, idx + 1);
    // 选择当前数
    if (target - candidates[idx] >= 0) {
        combine.add(candidates[idx]);
        dfs(candidates, target - candidates[idx], ans, combine, idx);
        combine.remove(combine.size() - 1);
    }
}

}

[joriscai]

思路

• 递归回溯
• 重复使用的剪枝

代码

javascript

/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  const res = [], path = []
  // 先排序
  candidates.sort()
  backtracking(0, 0)
  return res

  function backtracking(j, sum) {
    if (sum > target) return
    if (sum === target) {
      res.push(Array.from(path))
      return
    }
    for (let i = j; i < candidates.length; i++) {
      const n = candidates[i]
      // 剪枝，当大于目标值跳过
      if (n > target - sum) continue
      path.push(n)
      sum += n
      backtracking(i, sum)
      path.pop()
      sum -= n
    }
  }
};
// @lc code=end

复杂度分析

• 时间复杂度：O(N^(target/min))，先排序，要nlogn。回溯查找时无剪枝则要N^(target/min)。
• 空间复杂度：O(target)，除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。

[ghost]

题目

39. Combination Sum

思路

DFS

代码

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

        def helper(diff, out, start):
            if diff == 0:
                res.append(out)

            if diff < 0: return

            for i in range(start, len(candidates)):
                helper(diff - candidates[i], out+[candidates[i]], i)

        helper(target, [], 0)

        return res

[falconruo]

思路: 方法一、回溯(Backtracking) + 剪枝 (Pruning)

复杂度分析: 方法一、

• 时间复杂度: O(N^(target/M)，N为candidates数, M为candidates中的最小值
• 空间复杂度: O(N), 辅助数组combine的大小

代码(C++):

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();

        vector<vector<int>> res;
        vector<int> combine;

        backTracking(candidates, 0, target, combine, res);

        return res;
    }
private:
    void backTracking(vector<int>& candidates, int idx, int target, vector<int>& combine, vector<vector<int>>& res) {
        if (target < 0) return;

        if (target == 0){
            res.push_back(combine);
            return;
        }

        for (int i = idx; i < candidates.size(); ++i) {
            combine.push_back(candidates[i]);
            backTracking(candidates, i, target - candidates[i], combine, res);
            combine.pop_back();
        }
    }
};

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    if (candidates == null || candidates.length == 0) {
      return res;
    }
    Arrays.sort(candidates);
    dfs(candidates, target, res, new ArrayList<>(), 0);
    return res;
  }

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

[florenzliu]

Explanation

• backtracking + pruning

Code

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(n, curr, start):
            if n < 0:
                return
            if n == 0:
                result.append(curr[:])
                return
            for i in range(start, len(candidates)):
                curr.append(candidates[i])
                backtracking(n - candidates[i], curr, i)
                curr.pop()
        result = []
        backtracking(target, [], 0)
        return result

Complexity

• Space: O(n^target/min)
• Time: O(target/min)