【Day 81 】2024-06-27 - 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] ]

[Martina001]

class Solution { List<List> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (null == candidates || candidates.length == 0) return res;
        // 排序和下面的判断nums[i-1] == nums[i] 是为了去除由于nums中的重复数据导致的结果重复
        Arrays.sort(candidates);
        getCombine2(candidates, 0, target);
        return res;
    }

    List<Integer> track = new ArrayList<>();

    private void getCombine2(int[] nums, int start, int target) {
        if (target == 0) {
            res.add(new ArrayList<>(track));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.add(nums[i]);
            getCombine2(nums, i + 1, target - nums[i]);
            track.remove(track.size() - 1);
        }
    }
}

[lxy1108]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        rs_list = [set() for _ in range(target)]
        for num in candidates:
            for target_val in range(target-num-1,-1,-1):
                for i in rs_list[target_val]:
                    rs_list[target_val+num].add(i+(num,))
            if num-1<target:
                rs_list[num-1].add(tuple([num]))
        return [list(l) for l in rs_list[-1]]

[smallppgirl]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(
            state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]
        ):
            """回溯算法：子集和 II"""
            # 子集和等于 target 时，记录解
            if target == 0:
                res.append(list(state))
                return
            # 遍历所有选择
            # 剪枝二：从 start 开始遍历，避免生成重复子集
            # 剪枝三：从 start 开始遍历，避免重复选择同一元素
            for i in range(start, len(choices)):
                # 剪枝一：若子集和超过 target ，则直接结束循环
                # 这是因为数组已排序，后边元素更大，子集和一定超过 target
                if target - choices[i] < 0:
                    break
                # 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
                if i > start and choices[i] == choices[i - 1]:
                    continue
                # 尝试：做出选择，更新 target, start
                state.append(choices[i])
                # 进行下一轮选择
                backtrack(state, target - choices[i], choices, i + 1, res)
                # 回退：撤销选择，恢复到之前的状态
                state.pop()

        state = []  # 状态（子集）
        candidates.sort()  # 对 candidates 进行排序
        start = 0  # 遍历起始点
        res = []  # 结果列表（子集列表）
        backtrack(state, target, candidates, start, res)
        return res

[CathyShang]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def backtracking(candidates,target,Sum,startIndex):
            if Sum==target:
                ans.append(temp[:])
                return
            if Sum>target:
                return
            for i in range(startIndex,len(candidates)):
                if i > startIndex and candidates[i] == candidates[i-1]: continue
                temp.append(candidates[i])
                Sum += candidates[i]
                backtracking(candidates,target,Sum,i+1)
                temp.pop()
                Sum -= candidates[i]
        candidates=sorted(candidates)
        backtracking(candidates,target,0,0)
        return ans

[Dtjk]

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

    if(target==0){
        ans.push_back(index);            
        return {};
    }

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

};

[zhiyuanpeng]

class Solution:
    def __init__(self):
        self.ans = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.target = target
        counter = collections.Counter(candidates)
        counter = list(counter.items())
        self.n = len(counter)
        self.dfs([], 0, 0, counter)
        return self.ans

    def dfs(self, path, acc, start, counter):
        if acc > self.target:
            return
        if acc == self.target:
            self.ans.append(path.copy())
            return
        for i in range(start, self.n):
            key, val = counter[i]
            if val <= 0:
                continue
            path.append(key)
            acc += key
            counter[i] = (key, val - 1)
            self.dfs(path, acc, i, counter)
            path.pop()
            acc -= key
            counter[i] = (key, val)