search

leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库
28 stars 0 forks source link

【Day 81 】2022-03-02 - 40 组合总数 II #91

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

40 组合总数 II

入选理由

暂无

题目地址

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

前置知识

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] ]

LannyX commented 2 years ago

思路

backtrack

代码


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

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

        for(int i = start; i < candidates.length; i++){
            if(target - candidates[i] < 0){
                break;
            }
            if(i > start && candidates[i] == candidates[i - 1]){
                continue;
            }
            track.add(candidates[i]);
            sum += candidates[i];
            backtrack(i + 1, sum, candidates, target, track);
            sum -= candidates[i];
            track.remove(track.size() - 1);
        }
    }
}
ZacheryCao commented 2 years ago

Idea

backtracking + prune

Code

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> cur;
        backtracking(ans, candidates, target, 0, cur);
        return ans;
    }

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

Complexity:

Time: O(2^N) Space: O(N)

zwx0641 commented 2 years ago 
class Solution {
public:
    vector<vector<int>> res;

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

        for (int i = index; i < candidates.size(); i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
                continue;
            comb.push_back(candidates[i]);
            used[i] = true;
            findComb(comb, candidates, used, target - candidates[i], i + 1);
            used[i] = false;
            comb.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> comb;
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        findComb(comb, candidates, used, target, 0);
        return res;
    }
};
CoreJa commented 2 years ago

思路

回溯+剪枝：比起LC: 40，这个题要求每个数字只能使用一次，而且不能有重复的情况。数字只使用一次比较容易想到，循环的时候传递dfs时传i+1即可，则每次dfs都是从candiates[i+1]开始遍历。但candidates可能会有重复的数字，比如[1,1,2,5]，而target是8，这种情况下第一个1搜到的答案会和第二个1搜到的答案部分重复(第1个1搜到的更全面)，所以可以对candidates排序，在遍历第二个1时规避candidates[i-1]==candidates[i]的情况，因为只需要跳过第二个1，所以同时还要满足i>cur。复杂度$O(n^{target/min})$

代码

class Solution:
    # 回溯+剪枝：比起LC: 40，这个题要求每个数字只能使用一次，而且不能有重复的情况。数字只使用一次比较容易想到，循环的时候
    # 传递dfs时传`i+1`即可，则每次dfs都是从`candiates[i+1]`开始遍历。但`candidates`可能会有重复的数字，比如
    # `[1,1,2,5]`，而`target`是8，这种情况下第一个1搜到的答案会和第二个1搜到的答案部分重复(第1个1搜到的更全面)，所以可以
    # 对`candidates`排序，在遍历第二个1时规避`candidates[i-1]==candidates[i]`的情况，因为只需要跳过第二个1，所以同时还
    # 要满足`i>cur`。复杂度$O(n^{target/min})$
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        n = len(candidates)

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

        dfs(0, target, [])
        return ans
falconruo commented 2 years ago

思路:

回溯模板+剪枝

复杂度分析:

代码(C++):

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if (candidates.size() == 0) return {};

        vector<vector<int>> res;
        vector<int> combine;

        sort(candidates.begin(), candidates.end());
        backTracking(candidates, 0, target, combine, res);
        return res;
    }
private:
    void backTracking(vector<int>& candidates, int start, int target, vector<int>& combine, vector<vector<int>>& res) {
        if (target < 0) return;
        if (target == 0) {
            res.push_back(combine);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            if (candidates[i] > target) break;

            combine.push_back(candidates[i]);
            backTracking(candidates, i + 1, target - candidates[i], combine, res);
            combine.pop_back();
        }
    }
};
Tesla-1i commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        n = len(candidates)

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

        dfs(0, target, [])
        return ans
Alexno1no2 commented 2 years ago 
# 回溯通用的模板：
# res = []
# def backtrack(路径, 选择列表):
#     if 满足结束条件:
#         res.append(路径)
#         return  

#     if 满足剪枝条件：
#       return

#     for 选择 in 选择列表:
#         做选择
#         backtrack(路径, 选择列表)
#         撤销选择

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

        res = []
        n = len(candidates)
        candidates.sort()
        backtrack([], 0, 0)
        return res
yan0327 commented 2 years ago 
func combinationSum2(candidates []int, target int) [][]int {
    out := [][]int{}
    sort.Ints(candidates)
    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++{
            if i>index &&candidates[i] == candidates[i-1]{
                continue
            }
            temp = append(temp,candidates[i])
            sum += candidates[i]
            dfs(temp,sum,i+1)
            sum -= candidates[i]
            temp = temp[:len(temp)-1]
        }
    }
    dfs([]int{},0,0)
    return out

}
xuhzyy commented 2 years ago 
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()

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

            for i in range(start, len(candidates)):
                if target < candidates[i]:
                    return

                if i > start and candidates[i] == candidates[i-1]:
                    continue

                path.append(candidates[i])
                backtack(path, i+1, target - candidates[i])
                path.pop()

        backtack([], 0, target)
        return res
mannnn6 commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(temp_list, temp_sum, index):
            if temp_sum > target:
                return
            if temp_sum == target:
                res.append(temp_list)
                return
            for i in range(index, n):
                if i > index and candidates[i] == candidates[i - 1]:
                    continue
                backtrack(temp_list + [candidates[i]], temp_sum + candidates[i], i + 1)

        res = []
        n = len(candidates)
        candidates.sort()
        backtrack([], 0, 0)
        return res
1149004121 commented 2 years ago
  1. 组合总和 II

思路

为了避免排列组合元素相同但顺序不同的情况，需要对candidates进行排序。因为元素可以重复去，为了避免已经遍历到后面元素接下来还取前面的元素，因此要记录一个位置pos；此外，如果该candidate已经用过一次了，应避免后面与它相同的再重复打头。

代码

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

function dfs(prev, candidates, target, res, pos){
    if(target === 0){
        res.push(prev.slice());
        return;
    };
    if(target < 0) return;
    for(let i = pos; i < candidates.length; i++){
        if(i > pos && candidates[i] === candidates[i - 1]) continue;
        prev.push(candidates[i]);
        dfs(prev, candidates, target - candidates[i], res, i + 1);
        prev.pop();
    };
    return;
}

复杂度分析

tongxw commented 2 years ago

思路

回溯 + 剪枝

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

        dfs(candidates, 0, target, ans, path);
        return ans;
    }

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

        for (int i=start; i<nums.length; i++) {
            if (target < nums[i]) {
                break;
            }

            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }

            path.add(nums[i]);
            dfs(nums, i + 1, target - nums[i], ans, path);
            path.remove(path.size() - 1);
        }
    }
}

TC: O(2^n * n) SC: O(2^n) + O(n)

rzhao010 commented 2 years ago 
class Solution {
    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, 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) {
            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, i + 1, len, target - candidates[i], path, res);

            path.removeLast();
        }
    }
}
moirobinzhang commented 2 years ago

Code:

public class Solution { public IList<IList> CombinationSum2(int[] candidates, int target) { IList<IList> combinationSum = new List<IList>();

        if (candidates == null || candidates.Length == 0)
        {
            return combinationSum;
        }

        Array.Sort(candidates);
        List<int> subset = new List<int>();
        CombinationDFSHelper(candidates, target, combinationSum, subset,  0);
        return combinationSum;
}

 public void CombinationDFSHelper(int[] candidates, int remianTarget, 
        IList<IList<int>> combinationSum,  List<int> subset, int startIndex)
    {
        if (remianTarget == 0)
        {
            if (!combinationSum.Any(c => c.SequenceEqual( (new List<int>(subset)))))
            {
                combinationSum.Add(new List<int>(subset));
            }
            return;
        }

        for (int i = startIndex; i< candidates.Length; i++)
        {
            if (remianTarget < candidates[i])
            {
                return;
            }

            subset.Add(candidates[i]);
            CombinationDFSHelper(candidates, remianTarget - candidates[i], combinationSum, subset, i + 1);
            subset.RemoveAt(subset.Count - 1);
        }

    }

}

zjsuper commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans  = []
        lens = len(candidates)
        if lens == 0:
            return []
        candidates.sort()

        def dfs(ans, remain,candi,index,temp):
            if remain <0:
                return 
            if remain == 0:
                ans.append(temp)
            if remain >0:
                for i in range(index,lens):
                    if i > index and candi[i] == candi[i-1]:
                        continue
                    dfs(ans,remain - candi[i],candidates,i+1,temp+[candi[i]])
        dfs(ans,target,candidates,0,[])
        return ans
cszys888 commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        def dfs(comb, residual, start):
            if residual == 0:
                result.append(comb[:])
            for i in range(start, n):
                value = candidates[i]
                if i > start and value == candidates[i - 1]:
                    continue
                if value <= residual:
                    comb.append(value)
                    dfs(comb, residual - value, i + 1)
                    comb.pop()
                else:
                    break
            return

        result = []
        n = len(candidates)
        dfs([], target, 0)
        return result

time complexity: O(n*2^n) space complexity: O(n)

wdwxw commented 2 years ago

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

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

}

Yrtryannn commented 2 years ago 
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);
        }
    }
}
haixiaolu commented 2 years ago 
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
zhangzz2015 commented 2 years ago

思路

关键点

代码

C++ Code:


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

        sort(candidates.begin(), candidates.end()); 

        int sum =0; 
        vector<int> onePath; 
        vector<vector<int>> ret; 
        backTrac(candidates, target, sum, onePath, ret, 0); 
        return ret; 
    }

    void backTrac(vector<int>& candidates, int target, int& sum, vector<int>& onePath, vector<vector<int>>& ret, int start)
    {
        if(sum == target)
        {
            ret.push_back(onePath); 
            return; 
        }
        for(int i=start; i< candidates.size(); i++)
        {
            if(i>start && candidates[i]==candidates[i-1]) continue; 
            if(sum+candidates[i]>target) break; 

            sum += candidates[i]; 

            onePath.push_back(candidates[i]);                 
            backTrac(candidates, target, sum, onePath, ret, i+1); 
            sum -=candidates[i]; 
            onePath.pop_back();             
        }                        
    }
};
charlestang commented 2 years ago

思路

回溯法，穷举所有的组合。为了方便剪枝，可以将数组先行排序，这样一旦总和超过 target，后面的搜索都可以省略。

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

代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        visited = [False] * n
        res = []
        candidates = sorted(candidates)

        def dfs(start: int, s: int, c: List[int]):
            if s == target:
                res.append(c)
                return
            if s > target:
                return
            last = 0
            for i in range(start, n):
                val = candidates[i]
                if not visited[i] and val != last:
                    last = val
                    visited[i] = True
                    dfs(i, s + val, c + [val])
                    visited[i] = False

        dfs(0, 0, [])

        return res
JudyZhou95 commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

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

    def backtrack(self, candidates, path, target):
        if target < 0:
            return
        if target == 0:
            self.res.append(path)
            return

        for i in range(len(candidates)):
            if i > 0 and candidates[i] == candidates[i-1]:
                continue
            self.backtrack(candidates[i+1:], path+[candidates[i]], target - candidates[i])
hdyhdy commented 2 years ago 
func combinationSum2(candidates []int, target int) (ans [][]int) {
    sort.Ints(candidates)
    var freq [][2]int
    for _, num := range candidates {
        if freq == nil || num != freq[len(freq)-1][0] {
            freq = append(freq, [2]int{num, 1})
        } else {
            freq[len(freq)-1][1]++
        }
    }

    var sequence []int
    var dfs func(pos, rest int)
    dfs = func(pos, rest int) {
        if rest == 0 {
            ans = append(ans, append([]int(nil), sequence...))
            return
        }
        if pos == len(freq) || rest < freq[pos][0] {
            return
        }

        dfs(pos+1, rest)

        most := min(rest/freq[pos][0], freq[pos][1])
        for i := 1; i <= most; i++ {
            sequence = append(sequence, freq[pos][0])
            dfs(pos+1, rest-i*freq[pos][0])
        }
        sequence = sequence[:len(sequence)-most]
    }
    dfs(0, target)
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
Myleswork commented 2 years ago

思路

框架就是回溯的框架，但是这题有一个不一样的地方：有重复元素，每个元素只能用一次；

也就是说，例如

[1,2,1,1],target=3

答案只有[1,2]、[1,1,1]

那么我们把这个例子抽象成递归树就可以发现：

同一根枝上是可以有重复元素的，例如[1,1,1]就是可行的，这三个1并不是同一个1，而是分别对应于candidates中的三个1

而同一树层是不允许有同一元素的，例如[2,1]就不可行，因为第二层已经有1了

那么我们如何解决这一问题，如下：

将原数组排序后，借助used数组：

if(i!=0&&candidates[i]==candidates[i-1]&&used[candidates[i]-1]==false) continue; //同一层不能重复

当当前元素和前一元素相等但当前元素对应值未被使用，说明当前元素与前一相同元素处于同一数层，不能再次使用，直接continue

还有一个就是剪枝，不然会TLE

代码

class Solution {
public:
    vector<int> cur;
    vector<vector<int>> res;
    vector<bool> used;
    void dfs(vector<int>& candidates,int start,int& target){
        if(target==0){
            res.push_back(cur);
        }
        for(int i=start;i<candidates.size()&&target>=candidates[i];i++){
            if(i!=0&&candidates[i]==candidates[i-1]&&used[candidates[i]-1]==false) continue; //同一层不能重复
            target-=candidates[i];
            cur.push_back(candidates[i]);
            used[candidates[i]-1]=true;  //同一枝可以重复
            dfs(candidates,i+1,target);
            target+=candidates[i];
            cur.pop_back();
            used[candidates[i]-1]=false;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        used.resize(50,false);
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,target);
        return res;
    }
};

复杂度分析

时间复杂度：不太好说

空间复杂度：O(n)

ChenJingjing85 commented 2 years ago 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backTrack(candidates, pos, target, res, tempList):
            if target < 0:
                return 
            if target == 0:
                res.append(tempList.copy())
                return
            for i in range(pos, len(candidates)):
                if i > pos and candidates[i] == candidates[i-1]: #i=pos时说明递归在加深， i>pos时才说明在遍历同一层的哥哥candidate
                    continue
                tempList.append(candidates[i])
                backTrack(candidates, i+1, target-candidates[i], res, tempList)
                tempList.pop()
        candidates.sort()
        res = []
        backTrack(candidates, 0, target, res, [])
        return res
kite-fly6618 commented 2 years ago

思路

回溯

代码

var combinationSum2 = function(candidates, target) {
    let path = []
    let res = [] 
    candidates.sort((a,b)=>a-b)

    var backtrack = (candidates,startindex,sum)=> {

        if(sum>target) return
        if(sum == target) {
            res.push(Array.from(path))
            return
        }
        let f = -1
        for(let i = startindex;i<candidates.length;i++) {
            if(sum>target||candidates[i] == f) continue
            path.push(candidates[i])
            f = candidates[i]
            sum+=candidates[i]
            backtrack(candidates,i+1,sum)
            sum-=candidates[i]
            path.pop()
        }
    }
    backtrack(candidates,0,0)
    return res
}

复杂度

空间复杂度:O(n)

Aobasyp commented 2 years ago

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

空间复杂度为 O(target/min)

dahaiyidi commented 2 years ago

Problem

[40. 组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/)

难度中等855

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

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

注意：解集不能包含重复的组合。

Note

Complexity

Python

C++

class Solution {
public:
    void dfs(vector<int>& candidates, int start, int target, vector<vector<int>>& res, vector<int> path){
        if(target == 0){
            res.emplace_back(path);
        }

        for(int i = start; i < candidates.size(); i++){
            // 同一层不能重复使用重复出现的数字，但是不同层是可以使用重复的数字，否则res会有重复的元素
            if(i > start && candidates[i] == candidates[i - 1]){
                continue;
            }

            if(candidates[i] > target){
                // 若candidates[i] > target， 则可以终止本层次，因为后面的元素会更大，更不符合要求
                break;
            }
            path.emplace_back(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i], res, path);
            path.pop_back();    
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        sort(candidates.begin(), candidates.end()); // 从低到高排序,以剪枝

        dfs(candidates, 0, target, res, path);
        return res;

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

callmeerika commented 2 years ago

思路

回溯 + 剪枝

代码

var combinationSum2 = function(candidates, target) {
    const res = []; path = [], len = candidates.length;
    candidates.sort();
    backtracking(0, 0);
    return res;
    function backtracking(sum, i) {
        if (sum > target) return;
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        let f = -1;
        for(let j = i; j < len; j++) {
            const n = candidates[j];
            if(n > target - sum || n === f) continue;
            path.push(n);
            sum += n;
            f = n;
            backtracking(sum, j + 1);
            path.pop();
            sum -= n;
        }
    }
};

复杂度

时间复杂度：O(n!)
空间复杂度：O(n)

Richard-LYF commented 2 years ago

class Solution: def init(self): self.paths = [] self.path = []

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    '''
    类似于求三数之和，求四数之和，为了避免重复组合，需要提前进行数组排序
    '''

    # 必须提前进行数组排序，避免重复
    candidates.sort()
    self.backtracking(candidates, target, 0, 0)
    return self.paths

def backtracking(self, candidates: List[int], target: int, sum_: int, start_index: int) -> None:

    # Base Case
    if sum_ == target:
        self.paths.append(self.path[:])
        return

    # 单层递归逻辑
    for i in range(start_index, len(candidates)):
        # 剪枝，同39.组合总和

        if sum_ + candidates[i] > target:
            return

        # 跳过同一树层使用过的元素
        if i > start_index and candidates[i] == candidates[i-1]:
            continue

        sum_ += candidates[i]
        self.path.append(candidates[i])
        self.backtracking(candidates, target, sum_, i+1)
        self.path.pop()             # 回溯，为了下一轮for loop
        sum_ -= candidates[i]       # 回溯，为了下一轮for loop
guangsizhongbin commented 2 years ago

func combinationSum2(candidates []int, target int) [][]int { var track []int var res [][]int var history map[int]bool history = make(map[int]bool) sort.Ints(candidates) backtracking(0, 0, target, candidates, track, &res, history) return res }

func backtracking(startIndex, sum, target int, candidates, track [] int, res [][]int, history map[int]bool){ // 终止条件 if sum == target { tmp := make([]int, len(track)) copy(tmp, track) // 拷贝 res=append(*res, tmp) // 放入结果集 return } if sum > target{return} // 回溯 // used[i - 1] == true, 说明同一树支candidates[i - 1]使用过 // used[i - 1] == false, 说明同一树层candidates[i - 1]使用过 for i := startIndex; i < len(candidates); i++ { if i >0 && candidates[i] == candidates[i - 1] && history[i-1] == false { continue } // 更新路径集合和sum track = append(track, candidates[i]) sum+=candidates[i] history[i] = true // 递归 backtracking(i+1, sum, target, candidates, track, res, history) // 回溯 track = track[:len(track) - 1] sum -= candidates[i] history[i] = false } }

zzzpppy commented 2 years ago 
class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, flag);
        return lists;
    }

    public void backTracking(int[] arr, int target, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
                continue;
            }
            flag[i] = true;
            sum += arr[i];
            deque.push(arr[i]);
            //每个节点仅能选择一次，所以从下一位开始
            backTracking(arr, target, i + 1, flag);
            int temp = deque.pop();
            flag[i] = false;
            sum -= temp;
        }
    }
}
Hacker90 commented 2 years ago

func combinationSum2(candidates []int, target int) [][]int { var track []int var res [][]int var history map[int]bool history = make(map[int]bool) sort.Ints(candidates) backtracking(0, 0, target, candidates, track, &res, history) return res }

func backtracking(startIndex, sum, target int, candidates, track [] int, res [][]int, history map[int]bool){ // 终止条件 if sum == target { tmp := make([]int, len(track)) copy(tmp, track) // 拷贝 res=append(*res, tmp) // 放入结果集 return } if sum > target{return} // 回溯 // used[i - 1] == true, 说明同一树支candidates[i - 1]使用过 // used[i - 1] == false, 说明同一树层candidates[i - 1]使用过 for i := startIndex; i < len(candidates); i++ { if i >0 && candidates[i] == candidates[i - 1] && history[i-1] == false { continue } // 更新路径集合和sum track = append(track, candidates[i]) sum+=candidates[i] history[i] = true // 递归 backtracking(i+1, sum, target, candidates, track, res, history) // 回溯 track = track[:len(track) - 1] sum -= candidates[i] history[i] = false } }

shamworld commented 2 years ago 
var combinationSum2 = function(candidates, target) {
    let result = [];
    let path = [];
    candidates.sort();
    const backTracking = (index,num) => {
        if(num > target) return;
        if(num === target){
            result.push(Array.from(path));
            return;
        }
        let f = -1;
        for(let i = index; i < candidates.length; i++){
            if(candidates[i] > target - num || f === candidates[i]) continue
            path.push(candidates[i]);
            num += candidates[i];
            f = candidates[i];
            backTracking(i+1,num);
            path.pop();
            num -= candidates[i]
        }

    }
    backTracking(0,0);
    return result;
};
yetfan commented 2 years ago

思路 回溯

代码

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()
fornobugworld commented 2 years ago

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

machuangmr commented 2 years ago

代码

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        if(len == 0) return res;
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path,res);
        return res;
    }
    public void dfs(int[] candidates, int begin, int legnth, int target, Deque<Integer> path, List<List<Integer>> res) {
        if(target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin;i <legnth;i++) {
            if(target - candidates[i] < 0) {
                break;
            }
            if(i > begin && candidates[i] == candidates[i -1]) {
                continue;
            }
            path.addLast(candidates[i]);
            dfs(candidates, i + 1, legnth, target - candidates[i], path,res);
            path.removeLast();
        }
    }
}
GaoMinghao commented 2 years ago 
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);
        }
    }
}
Rex-Zh commented 2 years ago

思路

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

}

hulichao commented 2 years ago

思路

代码

复杂度分析

hulichao commented 2 years ago

思路

回溯

代码

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, flag);
        return lists;
    }

    public void backTracking(int[] arr, int target, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
                continue;
            }
            flag[i] = true;
            sum += arr[i];
            deque.push(arr[i]);
            //每个节点仅能选择一次，所以从下一位开始
            backTracking(arr, target, i + 1, flag);
            int temp = deque.pop();
            flag[i] = false;
            sum -= temp;
        }
    }
}

复杂度分析

herbertpan commented 2 years ago

思路

  1. 标准recursive + 去重

    code

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

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

    return ans;
}

private void helper(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> ans) {
    if (target == 0) {
        ans.add(new ArrayList<>(path));
        return;
    }
    if (target < 0 || start == candidates.length) {
        return;
    }

    // iterate all options
    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) {
             continue;
        }
        int curr = candidates[i];
        path.add(curr);

        helper(candidates, target - curr, i + 1, path, ans);

        path.remove(path.size() - 1);
    }
}
}

    complexity

  2. time: O((target / minElement) ^ 2)
  3. space: O((target / minElement) ^ 2)
declan92 commented 2 years ago

java

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

    public void backtrack(List<List<Integer>> res, List<Integer> temp, int[] candidates, int target, Set<Integer> set,int start) {
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        int val = 0;
        for (int i = start; i < candidates.length; i++) {
            if (set.contains(i)) 
                continue;
            if (candidates[i]==val)
                continue;
            if (candidates[i] > target)
                break;
            temp.add(candidates[i]);
            set.add(i);
            backtrack(res, temp, candidates, target - candidates[i], set, i);
            val = temp.get(temp.size()-1);
            temp.remove(temp.size() - 1);
            set.remove(i);
        }
    }
}

时间:$O(n^{target/min})$,n为数组长度,感觉复杂度小于$O(n*2^n)$ 空间:$O(target/min)$,递归栈深度为target/min,set的长度最长不超过target/min;

zuiaiqun commented 2 years ago 

func combinationSum2(candidates []int, target int) [][]int {
    var res [][]int
    sort.Slice(candidates, func(i, j int) bool {
        if candidates[i] < candidates[j] {
            return true
        }
        return false
    })
    dfs_40(candidates, target, 0, nil, 0, &res)
    return res
}

func dfs_40(nums []int, target int, start int, curNums []int, curTotal int, res *[][]int) {
    if curTotal == target {
        tmp := make([]int, len(curNums))
        copy(tmp, curNums)
        *res = append(*res, tmp)
        return
    }
    for i := start; i < len(nums); i++ {
        if curTotal + nums[i] > target {
            continue
        }
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        curTotal += nums[i]
        curNums = append(curNums, nums[i])
        dfs_40(nums, target, i+1, curNums, curTotal, res)
        curTotal -= nums[i]
        curNums = curNums[:len(curNums)-1]
    }
}