【Day 81 】2023-01-20 - 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] ]

[mayloveless]

思路

对比组合总数1，有重复数据，只能使用一次。递归时i+1，则是指使用一次，如果和上一个重复，需要跳过。

代码

var combinationSum2 = function(candidates, target) {
    const nums = candidates.sort((a,b) => a-b);// 重复的在一起
    const res = [];
    var combineFunc = function(count, path) {
        const sum = _.sum(path);
        if (sum > target) return;
        if (sum === target) {
            res.push([...path]);
            return;
        }
        for (let i = count;i<nums.length;i++) {
            // 重复的可以不必递归
            if (i !== count && nums[i-1] === nums[i]) continue;
            path.push(nums[i]);
            combineFunc(i+1,[...path])// 只能用1次
            path.pop();
        }
    }
    combineFunc(0, []);
    return res;
};

复杂度

时间：O(2^n*n)最大 空间：O(n)

[snmyj]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        n = len(candidates)
        min_ele,max_ele = candidates[0],candidates[-1]
        def sumup(nums=[],acc=0,head=0,deep=0):
            select = 0
            if acc + min_ele > target: return
            if acc + max_ele*(n-head) <target: return
            for i in range(head,n):
                x=candidates[i]
                if x == select: continue
                new_acc=acc+x
                new_nums=nums+[x]
                if new_acc < target: 
                    if sumup(new_nums,new_acc,i+1,deep+1):
                        select = x
                if new_acc == target: 
                    if not ans or ans[-1] != new_nums:
                        ans.append(new_nums)
                    return True
            return select!=0
        sumup()
        return ans

[FlipN9]

/**
    Each number in candidates may only be used once in the combination.
    1. 记录出现次数
    2. 优化: freq根据数从小到大排序, 这样递归到一个数时, 如果该数大于 rest, 
            后面的 还未递归的数也大于 rest, 就不需要再进行选择了

    TC: O(2^N * N)  SC: O(N) --> freq, 当前选择的列表, 栈
*/
class Solution {
    int[] freq = new int[51];
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        for (int x : candidates)
            freq[x]++;
        dfs(1, target);
        return res;
    }

    private void dfs(int s, int rest) {
        if (rest == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        if (s == freq.length || s > rest)
            return;
        // 不选
        dfs(s + 1, rest);
        // 选
        int most = Math.min(freq[s], rest / s);
        for (int i = 1; i <= most; i++) {
            tmp.add(s);
            dfs(s + 1, rest - s * i);
        }
        for (int i = 1; i <= most; i++) {
            tmp.remove(tmp.size() - 1);
        }
    }
}

[bookyue]

code

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

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

[klspta]

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

    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.addLast(candidates[i]);
            dfs(candidates, len, i + 1, target - candidates[i], path, res);
            path.removeLast();
        }
    }

[whoam-challenge]

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(pos: int, rest: int): nonlocal sequence if rest == 0: ans.append(sequence[:]) return if pos == len(freq) or rest < freq[pos][0]: return

        dfs(pos + 1, rest)

        most = min(rest // freq[pos][0], freq[pos][1])
        for i in range(1, most + 1):
            sequence.append(freq[pos][0])
            dfs(pos + 1, rest - i * freq[pos][0])
        sequence = sequence[:-most]

    freq = sorted(collections.Counter(candidates).items())
    ans = list()
    sequence = list()
    dfs(0, target)
    return ans

[Elon-Lau]

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(pos: int, rest: int): nonlocal sequence if rest == 0: ans.append(sequence[:]) return if pos == len(freq) or rest < freq[pos][0]: return

    dfs(pos + 1, rest)

    most = min(rest // freq[pos][0], freq[pos][1])
    for i in range(1, most + 1):
        sequence.append(freq[pos][0])
        dfs(pos + 1, rest - i * freq[pos][0])
    sequence = sequence[:-most]

freq = sorted(collections.Counter(candidates).items())
ans = list()
sequence = list()
dfs(0, target)
return ans

[RestlessBreeze]

code

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

[tiandao043]

思路

与 组合总和 的区别是一个只能用一次，也是先排序，代码区别是i从ii+1计数，光这样的话，125会出现两遍，所以只要和上一个重复可以跳过。 在搜索（dfs）过程中，若该元素和前一个元素相等，那么因为前一个元素打头的解都已经搜所完毕了，因此没必要在搜这个元素了，故 pass。

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> index;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target, int ii=-1) {
        sort(candidates.begin(),candidates.end());

        if(target==0){
            ans.push_back(index);            
            return {};
        }
        // if(target<candidates[ii]){           
        //     return {};
        // }
        // cout<<ii<<candidates[ii]<<endl;
        for(int i=ii+1;i<candidates.size();i++){
            if(target<candidates[i]){break;}
            if(i>ii+1&&candidates[i]==candidates[i-1]){
                continue;
            }
            index.push_back(candidates[i]);
            combinationSum2(candidates,target-candidates[i],i);
            index.pop_back();
        }
        return ans;
    }
};

O(2^n×n) O(n)

[paopaohua]

public List<List<Integer>> 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<Integer>> res, List<Integer> 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);
        }
    }
}

[saitoChen]

var combinationSum2 = function(num, target) {
  const len = num.length;
  let res = [];
  if(len === 1) {
      if(num[0] === target) {
          res.push(num);
          return res;
      }else return res;
  }
  num.sort((a, b) => a - b);
  dfs(0,target,0,[]);
  return res;
  // dep层数 t目标值  cur当前的总和 resArr当前可以的数集合
  function dfs(dep, t, cur, resArr) {
      if(cur === t) {
        res.push([...resArr]);
        return;
      }
      if(dep >= len) return;
      if(cur > t) return;

      // select
      let val = num[dep];
      resArr.push(val);
      dfs(dep + 1, t, cur + val, resArr);
      resArr.pop();

      // no
      while(dep < len && num[dep] === val) dep++;
      dfs(dep, t, cur, resArr);
  }

[Alexno1no2]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(tmp, cur, index):
            if cur > target:
                return
            if cur == target:
                res.append(tmp)
                return
            for i in range(index, n):
                if i > index and candidates[i] == candidates[i - 1]:
                    continue
                backtrack(tmp + [candidates[i]], cur + candidates[i], i + 1)

        res = []
        n = len(candidates)
        candidates.sort()
        backtrack([], 0, 0)
        return res

[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; // ch 记录选择的数字。
        solve(0, candidates, 0, ch, target, ans);
        return ans;
    }
};

[Elsa-zhang]

# 40 组合总数 II
''' 给定一个无重复元素的数组 candidates 和一个目标数 target, 找出 candidates 中所有可以使数字和为 target 的组合
    candidates 中的每个数字在每个组合中只能使用一次
    回溯
'''

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

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

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

                templist.append(candidate[i])
                backtrack(ans, templist, candidate, remain-candidate[i], i+1) # 不能重复所以是i+1
                templist.pop()

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

        # ans_filter = []
        # for a in ans:
        #     if sorted(a) not in ans_filter:
        #         ans_filter.append(sorted(a))

        return ans

[Ryanbaiyansong]

class Solution:
    def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()
        print(nums)
        def dfs(start: int, path: List[int], cur: int):
            if cur == target:
                res.append(path[:])
            if cur > target:
                return 
            if start == n:
                return 

            for i in range(start, n):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                dfs(i + 1, path, cur + nums[i])
                path.pop()

        dfs(0, [], 0)
        # 1 1 2 3
        #         1 
        #     1     2    3 
        #   2  3    3
        #   3  

        #    1
        #  2  3
        #  3 
        return res

        #
        #