【Day 81 】2023-05-05 - 40 组合总数 II

[azl397985856]

40 组合总数 II

入选理由

暂无

题目地址

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

前置知识

• 剪枝
• 数组
• 回溯

  题目描述

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

candidates 中的每个数字在每个组合中只能使用一次。

说明：

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

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

[kofzhang]

思路

回溯法

复杂度

时间复杂度：O(n*2^n)，copy是n，回溯是2^n 空间复杂度：O(n) 存储临时列表

代码

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

        c = list(Counter(candidates).items())
        l = len(c)
        res = []

        def dfs(index,reminder,curlist):            
            if reminder==0:
                res.append(curlist.copy())
                return            
            if index==l or reminder<0:
                return
            val,times = c[index]
            for i in range(times+1):                
                curlist.extend([val]*i)
                dfs(index+1,reminder-val*i,curlist)
                for j in range(i):
                    curlist.pop()

        dfs(0,target,[])
        return res

[RestlessBreeze]

code

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

    void backtrack(vector<int>& candidates, int startindex, int cursum, int target, vector<int>& used)
    {
        if (startindex >= candidates.size() ||cursum >= target)
        {
            if (cursum == target)
                res.push_back(path);
            return;
        }
        for (int i = startindex; i < candidates.size(); i++)
        {
            if (i > 0 && used[i - 1] == 0 && candidates[i] == candidates[i - 1])
                continue;
            used[i] = 1;
            path.push_back(candidates[i]);
            backtrack(candidates,i + 1, cursum + candidates[i], target, used);
            path.pop_back();
            used[i] = 0;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> used(candidates.size(), 0);
        backtrack(candidates, 0, 0, target, used);
        return res;
    }
};

[LIMBO42]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        vec = []
        n = len(candidates)
        used = [False] * n
        ans = []
        def dfs(vec, start, num, used):
            if num == 0:
                ans.append(vec[:])
                return
            if start >= n or num < 0:
                return
            for i in range(start, n):
                if i >= 1 and candidates[i] == candidates[i-1] and used[i-1] == False:
                    continue
                if used[i] == False:
                    used[i] = True
                    vec.append(candidates[i])
                    dfs(vec, i+1, num-candidates[i], used)
                    used[i] = False
                    vec.pop()
        dfs(vec, 0, target, used)
        return ans

[bookyue]

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

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

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

            if (i > idx && candidates[i] == candidates[i - 1]) continue;

            path.addLast(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i], path, ans);
            path.removeLast();
        }
    }
}

[csthaha]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
  const res = [];
  const visited = new Array(candidates.length).fill(false);
  const backTrack = (path, start) => {
    const total = path.reduce((a, b) => a + b, 0);
    if (total > target) return;
    if (total === target) {
      res.push(path.slice());
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (
        visited[i] ||
        (i > start && candidates[i] === candidates[i - 1] && !visited[i - 1])
      ) {
        continue;
      }
      path.push(candidates[i]);
      visited[i] = true;
      backTrack(path, i + 1);
      path.pop();
      visited[i] = false;
    }
  };
  candidates.sort((x, y) => x - y);
  backTrack([], 0);
  return res;
};

[lp1506947671]

class Solution:
    def combinationSum2(self, candidates, target):
        lenCan = len(candidates)
        if lenCan == 0:
            return []
        candidates.sort()
        path = []
        res = []
        self.backtrack(candidates, target, lenCan, 0, 0, path, res)
        return res

    def backtrack(self, curCandidates, target, lenCan, curSum, indBegin, path, res):
            # 终止条件
            if curSum == target:
                res.append(path.copy())
            for index in range(indBegin, lenCan):
                nextSum = curSum + curCandidates[index]
                # 减枝操作
                if nextSum > target:
                    break
                # 通过减枝避免重复解的出现
                if index > indBegin and curCandidates[index-1] == curCandidates[index]:
                    continue
                path.append(curCandidates[index])
                # 由于元素只能用一次，所以indBegin = index+1
                self.backtrack(curCandidates, target, lenCan, nextSum, index+1, path, res)
                path.pop()

复杂度分析

• 时间复杂度：在最坏的情况下，数组中的每个数都不相同，数组中所有数的和不超过 target，那么每个元素有选和不选两种可能，一共就有 2^n种选择，又因为我们每一个选择，最多需要 O(n) 的时间 push 到结果中。因此一个粗略的时间复杂度上界为 O(N*2^N)，其中 N 是数组长度。更加严格的复杂度意义不大，不再分析。

• 空间复杂度：递归调用栈的长度不大于target/mintarget/min，同时用于记录路径信息的 list 长度也不大于 target/mintarget/min，因此空间复杂度为 O(target/min)

[Abby-xu]

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

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

[FireHaoSky]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(begin, path, residue):
            if residue == 0:
                res.append(path[:])
                return

            for index in range(begin, size):
                if candidates[index] > residue:
                    break

                if index > begin and candidates[index - 1] == candidates[index]:
                    continue

                path.append(candidates[index])
                dfs(index + 1, path, residue - candidates[index])
                path.pop()

        size = len(candidates)
        if size == 0:
            return []

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

[chocolate-emperor]

class Solution {
public:
    //因为要输出方案，所以需要用搜索
    // 1 1 2 5  1 1 5  2 5
    vector<vector<int>> res;
    vector<int>nums;
    void backtrack(vector<int>&curr,int target,int currSum,int index){
        if(currSum>target)  return;
        else if(currSum == target){
            res.emplace_back(curr);
        }

        int  l = nums.size();
        if(index==l)  return;

        for(int i = index; i<l ;i++){
            if(i>index && nums[i]==nums[i-1])   continue;
            curr.emplace_back(nums[i]);
            backtrack(curr,target,currSum+nums[i],i+1);
            curr.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        nums = vector<int>(candidates.begin(),candidates.end());
        vector<int>tmp;
        backtrack(tmp,target,0,0);
        return res;
    }
};

[zhangyu1131]

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        set<vector<int>> res_set;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end());
        backTrace(candidates, target, res_set, tmp, 0);

        return vector<vector<int>>(res_set.begin(), res_set.end());
    }
private:
    void backTrace(vector<int>& candidates, int target, set<vector<int>>& res_set, vector<int>& tmp, int start_idx)
    {
        if (target == 0)
        {
            vector<int> tmp_1(tmp);
            sort(tmp_1.begin(), tmp_1.end());
            res_set.insert(tmp_1);
            return;
        }

        int n = candidates.size();
        for (int i = start_idx; i < n; ++i)
        {
            if (i > start_idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (target >= candidates[i])
            {
                tmp.push_back(candidates[i]);
                backTrace(candidates, target - candidates[i], res_set, tmp, i + 1);
                tmp.pop_back();
            }
            else
            {
                break;
            }
        }
    }
};

[aoxiangw]

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

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

            for i in range(s, len(candidates)):
                if i > s and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                backtrack(i + 1, target - candidates[i], path)
                path.pop()

        backtrack(0, target, [])
        return res

[snmyj]

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
       sort(candidates.begin(),candidates.end());
       dfs(candidates,target,0,0);
       return ans; 
    }
    void dfs(vector<int>& candidates, int target,int sum,int index){
        if(sum>target) return;
        if(sum==target) ans.push_back(temp);
        for(int i=index;i<candidates.size()-1;i++){
            if(i!=candidates.size()-1&&candidates[i+1]==candidates[i]) continue;
            temp.push_back(candidates[i]);
            sum+=candidates[i];
            dfs(candidates,target,sum,i+1);
            sum-=candidates[i];
            temp.pop_back();

        }
    }
};

[chanceyliu]

代码

function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);
  const resArr: number[][] = [];
  function backTracking(
    candidates: number[],
    target: number,
    curSum: number,
    startIndex: number,
    route: number[]
  ) {
    if (curSum > target) return;
    if (curSum === target) {
      resArr.push(route.slice());
      return;
    }
    for (let i = startIndex, length = candidates.length; i < length; i++) {
      if (i > startIndex && candidates[i] === candidates[i - 1]) {
        continue;
      }
      let tempVal: number = candidates[i];
      route.push(tempVal);
      backTracking(candidates, target, curSum + tempVal, i + 1, route);
      route.pop();
    }
  }
  backTracking(candidates, target, 0, 0, []);
  return resArr;
}

[SoSo1105]

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

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

        for i in range(s, len(candidates)):
            if i > s and candidates[i] == candidates[i - 1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, target - candidates[i], path)
            path.pop()

    backtrack(0, target, [])
    return res

[harperz24]

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

    def backtrack(self, candidates, remain, start, comb, res):
        if remain == 0:
            res.append(list(comb))
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            temp = remain - candidates[i]
            if temp < 0:
                break

            comb.append(candidates[i])
            self.backtrack(candidates, temp, i + 1, comb, res)
            comb.pop()

[wangqianqian202301]

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

        candidates = sorted(candidates)
        return self.rec_combinations([], candidates, target)

    def rec_combinations(self, comb, candidates, target):
        res = []
        if sum(candidates) < target:
            return res
        if target == 0:
            res = [comb]
            return res

        for i, c in enumerate(candidates):
            if i > 0 and candidates[i-1] == c:
                continue

            if c <= target:
                res += self.rec_combinations(comb+[c], candidates[i+1:], target-c)
            if c > target:
                break

        return res

[kangliqi1]

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

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

}

public void helper(List<List> res, List list, int target, int[] candidates, int start) {

if (target == 0) {
    res.add(new LinkedList<>(list));
    return;
}

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

    if (target - candidates[i] >= 0) {

        if (i > start && candidates[i] == candidates[i - 1])
            continue;

        list.add(candidates[i]);
        helper(res, list, target - candidates[i], candidates, i + 1);
        list.remove(list.size() - 1);
    }
}

}

[X1AOX1A]

class Solution: def combinationSum2(self, candidates, target): lenCan = len(candidates) if lenCan == 0: return [] candidates.sort() path = [] res = [] self.backtrack(candidates, target, lenCan, 0, 0, path, res) return res

def backtrack(self, curCandidates, target, lenCan, curSum, indBegin, path, res):
        # 终止条件
        if curSum == target:
            res.append(path.copy())
        for index in range(indBegin, lenCan):
            nextSum = curSum + curCandidates[index]
            # 减枝操作
            if nextSum > target:
                break
            # 通过减枝避免重复解的出现
            if index > indBegin and curCandidates[index-1] == curCandidates[index]:
                continue
            path.append(curCandidates[index])
            # 由于元素只能用一次，所以indBegin = index+1
            self.backtrack(curCandidates, target, lenCan, nextSum, index+1, path, res)
            path.pop()

[Diana21170648]

思路

剪枝排序，需要把重复数字跳过

class Solution:
    def backtrack(self,curc,t,len,cursum,inbegin,path,res):
        if cursum==t:
            res.append(path.copy())
        for index in range(inbegin,len):
            nextsum=cursum+curc[index]
            if nextsum>t:
                break
            if index>inbegin and curc[index-1]==curc[index]:
                continue#继续执行剪枝
            path.append(curc[index])
            self.backtrack(curc,t,len,nextsum,index+1,path,res)
            path.pop()          
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n=len(candidates)
        if n==0:
            return[]
        candidates.sort()
        path=[]
        res=[]
        self.backtrack(candidates,target,n,0,0,path,res)
        return res

**复杂度分析**

[JasonQiu]

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

        def dfs(residue, start, path):
            if residue == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > residue:
                    break
                if i > start and candidates[i - 1] == candidates[i]:
                    continue
                path.append(candidates[i])
                dfs(residue - candidates[i], i + 1, path)
                path.pop()

        dfs(target, 0, [])
        return result

[lp1506947671]

class Solution:
    def combinationSum2(self, candidates, target):
        lenCan = len(candidates)
        if lenCan == 0:
            return []
        candidates.sort()
        path = []
        res = []
        self.backtrack(candidates, target, lenCan, 0, 0, path, res)
        return res

    def backtrack(self, curCandidates, target, lenCan, curSum, indBegin, path, res):
            # 终止条件
            if curSum == target:
                res.append(path.copy())
            for index in range(indBegin, lenCan):
                nextSum = curSum + curCandidates[index]
                # 减枝操作
                if nextSum > target:
                    break
                # 通过减枝避免重复解的出现
                if index > indBegin and curCandidates[index-1] == curCandidates[index]:
                    continue
                path.append(curCandidates[index])
                # 由于元素只能用一次，所以indBegin = index+1
                self.backtrack(curCandidates, target, lenCan, nextSum, index+1, path, res)
                path.pop()

复杂度分析

• 时间复杂度：在最坏的情况下，数组中的每个数都不相同，数组中所有数的和不超过 target，那么每个元素有选和不选两种可能，一共就有 2^n2n种选择，又因为我们每一个选择，最多需要 O(n) 的时间 push 到结果中。因此一个粗略的时间复杂度上界为 O(N*2^N)，其中 N 是数组长度。更加严格的复杂度意义不大，不再分析。
• 空间复杂度：递归调用栈的长度不大于target/mintarget/min，同时用于记录路径信息的 list 长度也不大于 target/mintarget/min，因此空间复杂度为 O(target/min)

[Lydia61]

40. 组合总数 Ⅱ

思路

生成树，剪枝

代码

class Solution:
    def combinationSum2(self, candidates, target) :
        def dfs(begin, path, residue):
            if residue == 0:
                res.append(path[:])
                return

            for index in range(begin, size):
                if candidates[index] > residue:
                    break

                if index > begin and candidates[index - 1] == candidates[index]:
                    continue

                path.append(candidates[index])
                dfs(index + 1, path, residue - candidates[index])
                path.pop()

        size = len(candidates)
        if size == 0:
            return []

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

[enrilwang]

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() vec = [] n = len(candidates) used = [False] * n ans = [] def dfs(vec, start, num, used): if num == 0: ans.append(vec[:]) return if start >= n or num < 0: return for i in range(start, n): if i >= 1 and candidates[i] == candidates[i-1] and used[i-1] == False: continue if used[i] == False: used[i] = True vec.append(candidates[i]) dfs(vec, i+1, num-candidates[i], used) used[i] = False vec.pop() dfs(vec, 0, target, used) return ans

[joemonkeylee]

思路

回溯

代码

function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => -b + a);
  const ans: number[][] = [];

  dfs(candidates, target, [], function (path: number[]) {
    return ans.push(path);
  });
  return ans;
}

function dfs(
  candidates: number[],
  target: number,
  path: number[],
  output: (path: number[]) => void
) {
  if (target === 0) {
    output(path);
    return;
  }

  for (const [index, can] of candidates.entries()) {
    if (target >= can) {
      if (
        !(candidates[index - 1] && candidates[index] === candidates[index - 1])
      ) {
        dfs(candidates.slice(index + 1), target - can, [...path, can], output);
      }
    } else {
      return;
    }
  }
}

复杂度分析

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

[Hughlin07]

class Solution {

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    if(candidates == null) {return result;}
    Arrays.sort(candidates);
    backtrack(candidates, result, list, target, 0);
    return result;    
}

private void backtrack(int[] candidates, List<List<Integer>> result, List<Integer> list, int target, int i){
    if(target < 0){
        return;
    }

    if(target == 0){
        result.add(new ArrayList<Integer>(list));
        return;
    }

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

        if(p > i && candidates[p-1] == candidates[p]){
            continue;
        }

        list.add(candidates[p]);
        backtrack(candidates, result, list, target-candidates[p], p + 1);
        list.remove(list.size()-1);
    }
}

}

[Jetery]

class Solution {
public:
    void solve(int i, vector<int>& candidates, int sum,
             vector<int>& ch, int target, vector<vector<int>>& ans) {
        if (sum == target) {
            ans.push_back(ch);
            return;
        }
        if (i == candidates.size() || sum > target)
            return;

        for (int j = i + 1; j < candidates.size(); j++)
            if (candidates[j] != candidates[i]) {
                solve(j, candidates, sum, ch, target, ans);
                break;
            }

        ch.push_back(candidates[i]);
        solve(i + 1, candidates, sum + candidates[i], ch, target, ans);
        ch.pop_back();
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        sort(candidates.begin(), candidates.end());
        vector<int> ch;
        solve(0, candidates, 0, ch, target, ans);
        return ans;
    }
};