【Day 81 】2023-08-29 - 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] ]

[freesan44]

class Solution {
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let lenCan = candidates.count
        if lenCan == 0 {
            return []
        }
        let sortedCandidates = candidates.sorted()
        var path = [Int]()
        var res = [[Int]]()
        backtrack(sortedCandidates, target, lenCan, 0, 0, &path, &res)
        return res
    }

    func backtrack(_ curCandidates: [Int], _ target: Int, _ lenCan: Int, _ curSum: Int, _ indBegin: Int, _ path: inout [Int], _ res: inout [[Int]]) {
        if curSum == target {
            res.append(path)
        }
        var index = indBegin
        while index < lenCan {
            let nextSum = curSum + curCandidates[index]
            if nextSum > target {
                break
            }
            if index > indBegin && curCandidates[index-1] == curCandidates[index] {
                index += 1
                continue
            }
            path.append(curCandidates[index])
            backtrack(curCandidates, target, lenCan, nextSum, index+1, &path, &res)
            path.removeLast()
            index += 1
        }
    }
}

[Diana21170648]

思路

回溯忘记pop了，老报错

代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n=len(candidates)
        if n==0:
            return []
        candidates.sort()
        temp=[]
        ans=[]
        def backtrack(curcandidates,target,n,curSum,indBgein,temp,ans):
            if curSum==target:
                ans.append(temp.copy())
            for i in range(indBgein,n):
                nextSum=curSum+curcandidates[i]
                if nextSum>target:
                    break
                if i>indBgein and  curcandidates[i-1]==curcandidates[i]:
                    continue
                temp.append(curcandidates[i])
                backtrack(curcandidates,target,n,nextSum,i+1,temp,ans)
                temp.pop()
        backtrack(candidates,target,n,0,0,temp,ans)
        return ans

复杂度分析

• 时间复杂度：O(N*2^n)，其中 N 为数组长度。
• 空间复杂度：O(Target/N)，递归调用栈深度和记录路径的长度

[Alexno1no2]

# 为了避免产生重复解，本题candidates需要排序

# backtrack步骤如下：
# 剪枝：如果当前tmp数组的和cur已经大于目标target，没必要枚举了，直接return
# 如果当前tmp数组的和cur正好和目标target相等，找到一个组合，加到结果res中去，并return
# for循环遍历从index开始的数，选一个数进入下一层递归。
# 如果从index开始的数有连续出现的重复数字，跳过该数字continue，因为这会产生重复解
# 因为数不可以重复选择，所以在进入下一层递归时，i要加1，从i之后的数中选择接下来的数

class Solution:
    def __init__(self):
        self.res = []
        # 记录回溯的路径
        self.track = []
        # 记录 track 中的元素之和
        self.trackSum = 0

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return self.res
        # 先排序，让相同的元素靠在一起
        candidates.sort()
        self.backtrack(candidates, 0, target)
        return self.res

    # 回溯算法主函数
    def backtrack(self, nums: List[int], start: int, target: int):
        # base case，达到目标和，找到符合条件的组合
        if self.trackSum == target:
            self.res.append(self.track[:])
            return
        # base case，超过目标和，直接结束
        if self.trackSum > target:
            return

        # 回溯算法标准框架
        for i in range(start, len(nums)):
            # 剪枝逻辑，值相同的树枝，只遍历第一条
            if i > start and nums[i] == nums[i - 1]:
                continue
            # 做选择
            self.track.append(nums[i])
            self.trackSum += nums[i]
            # 递归遍历下一层回溯树
            self.backtrack(nums, i + 1, target)
            # 撤销选择
            self.track.pop()
            self.trackSum -= nums[i]

[Fuku-L]

代码

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for(int num:candidates){
            int size = freq.size();
            if(freq.isEmpty() || num != freq.get(size - 1)[0]){
                freq.add(new int[]{num, 1});
            } else {
                freq.get(size - 1)[1]++;
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest){
        if(rest == 0){
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if(pos == freq.size() || rest < freq.get(pos)[0]){
            return;
        }

        dfs(pos + 1, rest);
        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for(int i = 1; i <= most; ++i){
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for(int i = 1; i <= most; ++i){
            sequence.remove(sequence.size() - 1);
        }
    }
}

[GuitarYs]

class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort() 
        res = []
        self.dfs(candidates, target, 0, [], res)
        return res

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