【Day 80 】2022-03-01 - 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

[hulichao]

思路

标准回溯模板搞定

代码

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

    private void backtrack(int[] candidates, int target, List<List<Integer>> res, int i, ArrayList<Integer> tmp_list) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(tmp_list));
            return;
        }
        for (int start = i; start < candidates.length; start++) {
            if (target < 0) break;
            //System.out.println(start);
            tmp_list.add(candidates[start]);
            //System.out.println(tmp_list);
            backtrack(candidates, target - candidates[start], res, start, tmp_list);
            tmp_list.remove(tmp_list.size() - 1);
        }
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[zwx0641]

class Solution {
public:
    vector<vector<int>> res;
    void findComb(vector<int>& comb, vector<int>& candidates, int target, int index) {
        if (target < 0) return;
        if (0 == target) {
            res.push_back(comb);
            return;
        }

        for (int i = index; i < candidates.size(); i++) {
            comb.push_back(candidates[i]);
            findComb(comb, candidates, target - candidates[i], i);
            comb.pop_back();
        }
    }

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

[CoreJa]

思路

• DP：这就是背包问题的回溯版，需要把得到target所需的内容保存起来，所以dp数组里存所需的内容即可，因为每次需要把上一格子的内容复制一遍，所以复杂度为$O(n(target/min)target)$
• 回溯+剪枝：用回溯直接去模拟每次拿取，要注意这里不应重复取用(所以回溯时应从i到n取用candidates)，递归树最大深度为$target/min$，所以最坏情况复杂度为$O(n^{target/min})$。

代码

class Solution:
    # DP：这就是背包问题的回溯版，需要把得到`target`所需的内容保存起来，所以dp数组里存所需的内容即可，因为每次需要把上一格
    # 子的内容复制一遍，所以复杂度为$O(n*(target/min)*target)$
    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]

    # 回溯+剪枝：用回溯直接去模拟每次拿取，要注意这里不应重复取用(所以回溯时应从`i`到`n`取用`candidates`)，递归树最大深度
    # 为$target/min$，所以最坏情况复杂度为$O(n^{target/min})$。
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        n = len(candidates)

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

        dfs(0, [], target)
        return ans

[zol013]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        def backtrack(i, curr_sum, curr_path):
            nonlocal ans
            if curr_sum == target:
                ans.append(curr_path[:])
                return
            if i >= len(candidates) or curr_sum > target:
                return 
            for j in range(i, len(candidates)):
                backtrack(j, curr_sum + candidates[j], curr_path + [candidates[j]])

        backtrack(0, 0, [])
        return ans

[LannyX]

思路

backtrack

代码

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

    void backtrack(int start, int n, int sum, int[] candidates, int target, List<Integer> temp){
        if(sum == target){
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        if(sum > target){
            return;
        }

        for(int i = start; i < n; i++){
            temp.add(candidates[i]);
            sum += candidates[i];
            backtrack(i, n, sum, candidates, target, temp);
            sum -= candidates[i];
            temp.remove(temp.size() - 1);
        }
    }
}

[xinhaoyi]

class Solution { List<List> res = new ArrayList<>(); //记录答案 List path = new ArrayList<>(); //记录路径

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    dfs(candidates,0, target);
    return res;
}
public void dfs(int[] c, int u, int target) {
    if(target < 0) return ;
    if(target == 0)
    {
        res.add(new ArrayList(path));
        return ;
    }
    for(int i = u; i < c.length; i++){
        if( c[i] <= target)  
        {
            path.add(c[i]);
            dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是i
            path.remove(path.size()-1); //回溯，恢复现场
        }
    }
}

}

[moirobinzhang]

Code:

public class Solution { public IList<IList> CombinationSum(int[] candidates, int target) { List<IList> res = new List<IList>(); List comSet = new List();

    Array.Sort(candidates);
    DFSHelper(candidates, comSet, res, target, 0);  

    return res;        
}

public void DFSHelper(int[] candidates, List<int> comSet,  List<IList<int>> res, int remaintarget, int startIndex)
{
    if (remaintarget == 0)
    {
        res.Add(new List<int>(comSet));
        return;        
    }

    for (int i = startIndex; i < candidates.Length; i++)
    {
        if (remaintarget < 0)
            break;

        if (i != startIndex && candidates[i] == candidates[i - 1])
            continue;

        comSet.Add(candidates[i]);
        DFSHelper(candidates, comSet, res, remaintarget - candidates[i], i);  
        comSet.RemoveAt(comSet.Count - 1);
    }

}

}

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

[ZacheryCao]

Idea

Backtracking

Code

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> cur;
        backtracking(candidates, 0, target, cur, ans);
        return ans;
    }

    void backtracking(vector<int>& candidates, int idx, int rest,vector<int>& cur, vector<vector<int>>& ans){
        if(rest<0)
            return;
        if(rest == 0)
            ans.push_back(cur);
        for(int i = idx; i<candidates.size(); ++i){
            cur.push_back(candidates[i]);
            backtracking(candidates, i, rest - candidates[i], cur, ans);
            cur.pop_back();
        }
    }
};

Complexity:

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

[Alexno1no2]

# 对candidates升序排序，以便只用向一个方向搜索；
# 递归求可能的组合。
# 每次递归时对所有candidates做一次遍历，
#1，满足条件，答案加入一条；
#2，不足，继续递归；
#3，超出，则直接退出。

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

        candidates = sorted(candidates)

        ans = []

        def find(s, res, target):
            for i in range(s, len(candidates)):
                c = candidates[i]
                if c == target:
                    ans.append(res + [c])
                if c < target:
                    find(i, res + [c], target - c)
                if c > target:
                    return
        find(0, [], target)

        return ans

[yan0327]

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

[Tesla-1i]

class Solution:
    # DP：这就是背包问题的回溯版，需要把得到`target`所需的内容保存起来，所以dp数组里存所需的内容即可，因为每次需要把上一格
    # 子的内容复制一遍，所以复杂度为$O(n*(target/min)*target)$
    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]

    # 回溯+剪枝：用回溯直接去模拟每次拿取，要注意这里不应重复取用(所以回溯时应从`i`到`n`取用`candidates`)，递归树最大深度
    # 为$target/min$，所以最坏情况复杂度为$O(n^{target/min})$。
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        n = len(candidates)

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

        dfs(0, [], target)
        return ans

[xuhzyy]

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []

        def backtrack(start, path, target):
            if target == 0:
                res.append(path[:])

            for i in range(start, len(candidates)):
                if target < 0:
                    break
                path.append(candidates[i])
                backtrack(i, path, target-candidates[i])
                path.pop()

        backtrack(0, [], target)
        return res

[1149004121]

39. 组合总和

思路

为了避免排列组合元素相同但顺序不同的情况，需要对candidates进行排序。因为元素可以重复去，为了避免已经遍历到后面元素接下来还取前面的元素，因此要记录一个位置pos。

代码

var combinationSum = function(candidates, target) {
    let res = [];
    candidates.sort((a, b) => a - b);
    dfs(res, [], candidates , target, 0);
    return res;
};

function dfs(res, list, candidates, target, pos){
    if(target === 0) res.push(list.slice());
    if(target < 0) return;

    for(let i = pos; i < candidates.length; i++){
        list.push(candidates[i]);
        dfs(res, list, candidates, target - candidates[i], i);
        list.pop();
    }
}

复杂度分析

• 时间复杂度：O(N^{target/min}) 。
• 空间复杂度：O(target/min) 。

[Myleswork]

思路

常规回溯

代码

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

    void backtrack(vector<int>& candidates,int target,int sum,int start){
        if(sum==target){
            res.push_back(cur);
            return;
        }
        for(int i = start;i<candidates.size() && sum<target;i++){
            sum+=candidates[i];
            cur.push_back(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum-=candidates[i];
            cur.pop_back();
        }
    }

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

复杂度分析

时间复杂度：O(candidates.len)

空间复杂度：O(candidates.len)

[rzhao010]

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

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

        for (int i = begin; i < len; i++) {
            path.add(candidates[i]);
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }

    }
}

[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)

[Moin-Jer]

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

}

[watchpoints]

class Solution {
public:
  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {

    vector<vector<int>> output;
    int len = candidates.size();
    if (0 == len) {
      return output;
    }
    vector<int> path;
    int sum = 0;
    int start = 0;
    dfs(candidates, target, sum, start, path, output);
    return output;
  }

  void dfs(vector<int> &candidates, int &target, int sum, int start,
           vector<int> &path, vector<vector<int>> &output) {

    if (sum == target) {
      output.push_back(path);
      return; //遗忘返回值，寻找目标就结束，递归推出条件你忘记啦 
              //你还是对个背包算法本质不清楚
    }
    if (start >= candidates.size() || sum > target) {
      return; // 你sb了 && 是同时成立的， 你还是对个背包算法本质不清楚
    }
      if (sum + candidates[start] <= target) {
      path.push_back(candidates[start]);
      dfs(candidates, target, sum + candidates[start], start, path, output);
      // path.back();// Returns a reference to the last element in the vector.
      // Removes the last element in the vector, effectively reducing the
      path.pop_back(); //对stl里面功能还是没有想清楚怎么用。模糊了害死人。
    }
    //不采用
    dfs(candidates, target, sum, start + 1, path, output);
  }
};

[charlestang]

思路

回溯法。

代码

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

        def dfs(i: int, c: List[int], s: int):
            for idx in range(i, n):
                num = candidates[idx]
                if num + s > target:
                    continue
                if num + s == target:
                    res.append(c + [num])
                    continue
                dfs(idx, c + [num], s + num)
        dfs(0, [], 0)

        return res

时间复杂度 O(n!)

[herbertpan]

思路

标准的dfs

code

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

        helper(candidates, target, 0, 0, new ArrayList<>(), ans);

        return ans;
    }

    private void helper(int[] candidates, int target, int index, int prevSum, List<Integer> prevPath, List<List<Integer>> ans) {
        if (prevSum == target) {
            ans.add(new ArrayList<>(prevPath));
            return;
        }
        if (index == candidates.length) {
            return;
        }

        int currCandidate = candidates[index];
        int maxForCurrCandidate = (target - prevSum) / currCandidate;

        for (int numOfCurrCandidate = 0; numOfCurrCandidate <= maxForCurrCandidate; numOfCurrCandidate++) {
            if (numOfCurrCandidate != 0) {
                prevPath.add(currCandidate);
            }

            helper(candidates, target, index + 1, prevSum + numOfCurrCandidate * currCandidate, prevPath, ans);
        }

        // return to init status
        for (int numOfCurrCandidate = 0; numOfCurrCandidate < maxForCurrCandidate; numOfCurrCandidate++) {
            prevPath.remove(prevPath.size() - 1);
        }

    }
}

complexity

1. time complexity: O(N ^ (target / candidate[i]))
2. space complexity: O(N ^ (target / candidate[i]))

[haixiaolu]

思路

回溯

• 递归两种情况： -- 选择当前元素 -- 不选择当前元素

代码

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

        def dfs(i, cur, total):
            # base case 1
            if total == target:
                res.append(cur.copy())
                return 
            # base case 2
            if i >= len(candidates) or total > target:
                return 

            cur.append(candidates[i])
            # case 1
            dfs(i, cur, total + candidates[i])
            cur.pop()
            # case 2
            dfs(i + 1, cur, total)

        dfs(0, [], 0)
        return res

复杂分析

• Time： O(n^t)
• Space: O(n)

[honeymeng-hub]

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

private void backtrack(int[] candidates, int target, List<List<Integer>> res, int i, ArrayList<Integer> tmp_list) {
    if (target < 0) return;
    if (target == 0) {
        res.add(new ArrayList<>(tmp_list));
        return;
    }
    for (int start = i; start < candidates.length; start++) {
        if (target < 0) break;
        //System.out.println(start);
        tmp_list.add(candidates[start]);
        //System.out.println(tmp_list);
        backtrack(candidates, target - candidates[start], res, start, tmp_list);
        tmp_list.remove(tmp_list.size() - 1);
    }
}

}

[baddate]

class Solution {
public:
    vector<int> temp;
    void Tback(vector<int>& candidates,int target,int n,int sum,vector<vector<int>>& v,int j){
        if(sum==target){                     
            v.push_back(temp);
            return ;
        }
        for(int i=j;i<n;i++){                 //从本身下标处开始遍历 防止重复
            if(sum+candidates[i]<=target){    //判断sum+candidates[i]是否进行录入
                temp.push_back(candidates[i]);
                Tback(candidates,target,n,sum+candidates[i],v,i);
                temp.pop_back();
            }
            else{                             //大于target直接回溯
                return ;
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        int n=candidates.size();
        vector<vector<int>> v;
        Tback(candidates,target,n,0,v,0);
        return v;
    }
};

[QinhaoChang]

思路 dfs + backtracking

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

    self.dfs(res, temp, candidates, target, 0)

    return res

def dfs(self, res, temp, candidates, target, index):
    if target == 0:
        res.append(temp.copy())
        return 

    if target < 0:
        return 

    for i in range(index, len(candidates)):
        temp.append(candidates[i])
        self.dfs(res, temp, candidates, target - candidates[i], i)
        temp.pop()

[cszys888]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        n = len(candidates)
        def dfs(comb, residual, start):
            if residual == 0:
                result.append(comb[:])
                return
            for i in range(start, n):
                value = candidates[i]
                if value <= residual:
                    comb.append(value)
                    dfs(comb, residual - value, i)
                    comb.pop()
                else:
                    break
            return

        dfs([],target, 0)
        return result

[Arya-03]

from typing import List

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

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

            for index in range(begin, size):
                dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])

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

[CodingProgrammer]

from typing import List

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

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

        for index in range(begin, size):
            dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])

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

[superduduguan]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] def backtrack(i, curr_sum, curr_path): nonlocal ans if curr_sum == target: ans.append(curr_path[:]) return if i >= len(candidates) or curr_sum > target: return for j in range(i, len(candidates)): backtrack(j, curr_sum + candidates[j], curr_path + [candidates[j]])

    backtrack(0, 0, [])
    return ans

[kite-fly6618]

思路

回溯+减枝

代码

var combinationSum = function(candidates, target) {
    var len = candidates.length
    let res = []
    let path = []
    candidates.sort((a,b)=>a-b)
    var backtrack = function(sum,candidates,target,startindex) {
        if (sum>target) return
        if (sum==target) {
            res.push([...path])
            return
        }
        for (let i = startindex;i <len;i++){
            sum +=candidates[i]
            if (sum>target) return
            path.push(candidates[i])
            backtrack(sum,candidates,target,i)
            sum-=candidates[i]
            path.pop()
        }

    }
    backtrack(0,candidates,target,0)
    return res
};

[ACcentuaLtor]

from typing import List

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

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

        for index in range(begin, size):
            dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])

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

[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()) # 将部分解空间合并到总体的解空间
            # 枚举所有以 i 为开始的部分解空间
            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;

[luhnn120]

思路

搜索回溯

代码

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(S) S为所有可行解的长度之和 空间复杂度 O(target)

[biscuit279]

思路：回溯

import copy
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def backtrace(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])
                backtrace(ans, tempList, candidates, remain - candidates[i], i)
                tempList.pop()
        ans = []
        backtrace(ans, [], candidates, target, 0)
        return ans

[last-Battle]

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tr;

        dfs(candidates, 0, 0, target, tr, res);

        return res;
    }

    void dfs(vector<int>& candidates, int sum, int start, int target, vector<int>& tr, vector<vector<int>>& res) {
        if (sum > target) {
            return;
        }

        if (sum == target) {
            res.emplace_back(tr);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            sum += candidates[i];
            tr.emplace_back(candidates[i]);

            dfs(candidates, sum, i, target, tr, res);

            sum -= candidates[i];
            tr.pop_back();
        }
    }
};

[hdyhdy]

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
        }
        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(target-candidates[idx], idx)
            comb = comb[:len(comb)-1]
        }
    }
    dfs(target, 0)
    return
}

[spacker-343]

思路

回溯, 保证生成序列为升序来去重

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target);
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    private void backtracking(int[] candidates, int target) {
        if (target == 0) {
            res.add(new LinkedList(path));
            return;
        }
        if (target < 0) {
            return;
        }
        int len = candidates.length;
        for (int i = 0; i < len; i++) {
            if (!path.isEmpty() && candidates[i] < path.peekLast()) {
                continue;
            }
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i]);
            path.removeLast();
        }
    }
}

[tian-pengfei]

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//        记录已存在的vector,去重使用
        unordered_set<string> has_set ;
        vector<int> path;
        vector<vector<int>> ans;
        int sum =0;
        dfs(ans,candidates,target,has_set,path,sum);
        return ans;

    }

    void dfs(vector<vector<int>>& ans,vector<int>& candidates,int& target,unordered_set<string> &has_set ,vector<int>& path,int &sum){
        if(sum==target){
            string key = getKey(path);
            if(has_set.find(key)==has_set.end()){
                ans.emplace_back(path);
                has_set.insert(key);
            }
            return ;
        }else if(sum>target)return ;
        for(auto & val:candidates){
            path.emplace_back(val);
            sum+=val;
            dfs(ans,candidates,target,has_set,path,sum);
            sum-=val;
            path.pop_back();
        }
    }

    string getKey(vector<int> ve){
        sort(ve.begin(),ve.end());
        string key = "";
        for (auto val:ve) {
            key+=("_"+to_string(val));
        }
        return key;
    }
};

[callmeerika]

思路

回溯

代码

var dfs = (candidates, index, n, target, path, res) => {
     if (target === 0) {
        res.push(Array.from(path));
        return;
    }
    for (let i = index; i < n; i++) {
        if (target - candidates[i] < 0) {
            break;
        }
        path.push(candidates[i]);
        dfs(candidates, i, n, target - candidates[i], path, res);
        path.pop();
    }
}
var combinationSum = function(candidates, target) {
    const n = candidates.length;
    const res = [];
    const path = [];
    candidates.sort((a, b)=> a - b);
    dfs(candidates, 0, n, target, path, res);
    return res;
};

复杂度

时间复杂度：O(S) 空间复杂度：O(target)

[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

}

[shamworld]

var combinationSum = function(candidates, target) {
    let result = [];
    let path = [];
    candidates.sort((a,b) => a-b);
    const backTracking = (index,num) => {
        if(num > target) return ;
        if(num === target){
            result.push(Array.from(path));
            return;
        }
        for(let i = index; i < candidates.length; i++){
            num += candidates[i];
            path.push(candidates[i]);
            backTracking(i,num);
            path.pop();
            num -= candidates[i];
        }
    }
    backTracking(0,0);
    return result;
};

[alongchong]

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

[yetfan]

思路 回溯 剪枝

代码

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()) # 将部分解空间合并到总体的解空间
            # 枚举所有以 i 为开始的部分解空间
            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;

[pwqgithub-cqu]

lass Solution { public: vector temp; void Tback(vector& candidates,int target,int n,int sum,vector<vector>& v,int j){ if(sum==target){
v.push_back(temp); return ; } for(int i=j;i<n;i++){ //从本身下标处开始遍历 防止重复 if(sum+candidates[i]<=target){ //判断sum+candidates[i]是否进行录入 temp.push_back(candidates[i]); Tback(candidates,target,n,sum+candidates[i],v,i); temp.pop_back(); } else{ //大于target直接回溯 return ; } } } vector<vector> combinationSum(vector& candidates, int target) { sort(candidates.begin(),candidates.end()); int n=candidates.size(); vector<vector> v; Tback(candidates,target,n,0,v,0); return v; } };

[Hacker90]

思路 回溯

代码 var dfs = (candidates, index, n, target, path, res) => { if (target === 0) { res.push(Array.from(path)); return; } for (let i = index; i < n; i++) { if (target - candidates[i] < 0) { break; } path.push(candidates[i]); dfs(candidates, i, n, target - candidates[i], path, res); path.pop(); } } var combinationSum = function(candidates, target) { const n = candidates.length; const res = []; const path = []; candidates.sort((a, b)=> a - b); dfs(candidates, 0, n, target, path, res); return res; };

[zzzpppy]

    List<List<Integer>> res = new ArrayList<>(); //记录答案
    List<Integer> path = new ArrayList<>();  //记录路径

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0, target);
        return res;
    }
    public void dfs(int[] c, int u, int target) {
        if(target < 0) return ;
        if(target == 0)
        {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = u; i < c.length; i++){
            if( c[i] <= target)  
            {
                path.add(c[i]);
                dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是i
                path.remove(path.size()-1); //回溯，恢复现场
            }
        }
    }
}

[googidaddy]

var dfs = (candidates, index, n, target, path, res) => { if (target === 0) { res.push(Array.from(path)); return; } for (let i = index; i < n; i++) { if (target - candidates[i] < 0) { break; } path.push(candidates[i]); dfs(candidates, i, n, target - candidates[i], path, res); path.pop(); } } var combinationSum = function(candidates, target) { const n = candidates.length; const res = []; const path = []; candidates.sort((a, b)=> a - b); dfs(candidates, 0, n, target, path, res); return res; };

[fornobugworld]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = list() road = list() def backtrack(candidates,i,road,summ,target): if summ == target: temp = [ for in road] ans.append(temp) return if summ > target: return for j in range(i,len(candidates)): road.append(candidates[j]) summ += candidates[j] backtrack(candidates,j,road,summ,target) road.pop() summ -= candidates[j] backtrack(candidates,0,road,0,target) return ans

[GaoMinghao]

public List<List<Integer>> combinationSum(int[] candidates, int target) {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new LinkedList<>();
    backtrack(res, list, candidates, target, 0);
    return res;
}

public void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int cur, int pos) {

    if (cur < 0)
        return;

    if (cur == 0) {

        res.add(new LinkedList<>(list));
        return;
    }

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

        list.add(candidates[i]);
        backtrack(res, list, candidates, cur - candidates[i], i);
        list.remove(list.size() - 1);
    }
}

[for123s]

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