[LeetCode] 40. 组合总和 II

题目链接 : https://leetcode-cn.com/problems/combination-sum-ii/

题目描述:

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

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

说明：

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

示例:

示例 1:

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

示例 2:

输入: candidates = [2,5,2],target = 5,[5]
]

思路

回溯算法

很标准的模板

关注我的知乎专栏,了解更多解题技巧,大家一起加油!

代码:

class Solution:
    def combinationSum2(self,candidates: List[int],target: int) -> List[List[int]]:
        if not candidates:
            return []
        candidates.sort()
        n = len(candidates)
        res = []
        
        def backtrack(i,tmp_sum,tmp_list):
            if tmp_sum == target:
                res.append(tmp_list)
                return 
            for j in range(i,n):
                if tmp_sum + candidates[j]  > target : break
                if j > i and candidates[j] == candidates[j-1]:continue
                backtrack(j + 1,tmp_sum + candidates[j],tmp_list + [candidates[j]])
        backtrack(0,[])    
        return res

java

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

    }

    private void backtrack(List<List<Integer>> res,int[] candidates,int target,int i,int tmp_sum,ArrayList<Integer> tmp_list) {
        if (tmp_sum == target) {
            res.add(new ArrayList<>(tmp_list));
            return;
        }
        for (int start = i; start < candidates.length; start++) {
            if (tmp_sum + candidates[start] > target) break;
            if (start > i && candidates[start] == candidates[start - 1]) continue;
            tmp_list.add(candidates[start]);
            backtrack(res,start + 1,tmp_sum + candidates[start],tmp_list);
            tmp_list.remove(tmp_list.size() - 1);
        }
    }
}

类似题目还有:

39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

这类题目都是同一类型的,用回溯算法!

其实回溯算法关键在于:不合适就退回上一步

然后通过约束条件,减少时间复杂度.

大家可以从下面的解法找出一点感觉!

78. 子集

class Solution:
    def subsets(self,nums):        
        if not nums:
            return []
        res = []
        n = len(nums)

        def helper(idx,temp_list):
            res.append(temp_list)
            for i in range(idx,n):
                helper(i + 1,temp_list + [nums[i]])

        helper(0,[])
        return res

90. 子集 II

class Solution(object):
    def subsetsWithDup(self,nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        n = len(nums)
        res = []
        nums.sort()
        # 思路1
        def helper1(idx,n,temp_list):
            if temp_list not in res:
                res.append(temp_list)
            for i in range(idx,n):
                helper1(i + 1,temp_list + [nums[i]])
        # 思路2
        def helper2(idx,n):
                if i > idx and  nums[i] == nums[i - 1]:
                    continue
                helper2(i + 1,temp_list + [nums[i]])

        helper2(0,[])
        return res

46. 全排列

class Solution(object):
    def permute(self,nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return
        res = []
        n = len(nums)
        visited = [0] * n
        def helper1(temp_list,length):
            if length == n:
                res.append(temp_list)
            for i in range(n):
                if visited[i] :
                    continue
                visited[i] = 1
                helper1(temp_list+[nums[i]],length+1)
                visited[i] = 0
        def helper2(nums,temp_list,length):
            if length == n:
                res.append(temp_list)
            for i in range(len(nums)):
                helper2(nums[:i]+nums[i+1:],temp_list+[nums[i]],length+1)
        helper1([],0)
        return res

47. 全排列 II

class Solution(object):
    def permuteUnique(self,nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        nums.sort()
        n = len(nums)
        visited = [0] * n
        res = []

        def helper1(temp_list,length):
            # if length == n and temp_list not in res:
            #   res.append(temp_list)
            if length == n:
                res.append(temp_list)
            for i in range(n):
                if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
                    continue
                visited[i] = 1
                helper1(temp_list + [nums[i]],length + 1)
                visited[i] = 0

        def helper2(nums,length):
            if length == n and temp_list not in res:
                res.append(temp_list)
            for i in range(len(nums)):
                helper2(nums[:i] + nums[i + 1:],temp_list + [nums[i]],length + 1)

        helper1([],0)
        # helper2(nums,[],0)
        return res

39.组合总和

class Solution(object):
    def combinationSum(self,target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        if min(candidates) > target:
            return []
        candidates.sort()
        res = []

        def helper(candidates,temp_list):
            if target == 0:
                res.append(temp_list)
            if target < 0:
                return
            for i in range(len(candidates)):
                if candidates[i] > target:
                    break
                helper(candidates[i:],target - candidates[i],temp_list + [candidates[i]])
        helper(candidates,[])
        return res

40. 组合总和 II

class Solution:
    def combinationSum2(self,[])    
        return res