欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

【回溯法】leetcode组合、排列

程序员文章站 2022-03-10 19:49:50
目录77. 组合46. 全排列47. 全排列 II39. 组合总和40. 组合总和 II216. 组合总和 III78. 子集90. 子集 II77. 组合给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。输入:n = 4, k = 2输出:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]这道题是比较简单的回溯法题目,这一题的解答模板就是回溯问题的基本模......

目录

77. 组合

46. 全排列

47. 全排列 II

 39. 组合总和 

40. 组合总和 II

216. 组合总和 III

78. 子集

90. 子集 II


77. 组合

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

这道题是比较简单的回溯法题目,这一题的解答模板就是回溯问题的基本模板

class Solution:
    def combine(self, n, k):
        output = []
        def huisu(lists,start):
            for i in range(start,n+1):
                new = lists + [i]
                if len(new) == k:
                    output.append(new)
                    continue
                huisu(new,i+1)      
        huisu([],1)
        return output

46. 全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 本题的要点在于每次递归输入的序列,要刨除当前数字:lists[0:index] + lists[index+1:]

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        output = []
        length = len(nums)

        def huisu(zuhe,lists):
            for index,num in enumerate(lists):
                new = zuhe + [num]  
                if len(new) == length:
                    output.append(new)
                else:
                    huisu(new,lists[0:index] + lists[index+1:])      
        huisu([],nums)
        return output

 47. 全排列 II

给定一个可包含重复数字的序列,返回所有不重复的全排列。

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

 本题与上一题的区别在于给出的数组里面含有重复的数字,因此首先要排序。之后给出两种方法

方法一:直接加上约束语句if new not in output,也就是不进行枝剪,速度较慢

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        output = []
        length = len(nums)

        def huisu(zuhe,lists):
            for index,num in enumerate(lists):
                new = zuhe + [num]  
                if len(new) == length and new not in output:
                    output.append(new)
                else:
                    huisu(new,lists[0:index] + lists[index+1:])      
        huisu([],nums)
        return output

 方法二:进行枝剪

if index > 0 and lists[index] == lists[index-1]:

每当进入新的构成,先考虑该构成的首字符是否和上一个一样,如果一样的话直接跳过

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        output = []
        length = len(nums)

        def huisu(zuhe,lists):
            for index,num in enumerate(lists):
                if index > 0 and lists[index] == lists[index-1]:
                    continue
                new = zuhe + [num]  
                if len(new) == length:
                    output.append(new)
                    return
                huisu(new,lists[0:index] + lists[index+1:])      
        huisu([],nums)
        return output

 39. 组合总和 

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。 
示例 1:输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:输入:candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

这道题的要点在于对原始的数组进行了排序,并且由于一个元素可以被重复的使用,所以每次递归的数组都要包含当前的元素

这里面涉及三个枝剪条件:

  1. 如果当前的数字num>res,说明后面的数字也不会满足要求,直接return
  2. 如果当前的组合new满足要求,将其添加到output中,则后面的数字也不会满足要求,直接return 
  3. 如果此时数组candidates的第一个元素大于res,也就意味下如果继续递归的话,下一次递归会加上candidates[0],必然会使得res<0,不满足要求。此时直接continue。
    例如将示例2中的target改为7,经过3次递归后new = [2,2,2],此时res = 1,而candidates 第一个数字仍为2>res,若继续递归的话,下一个new为[2,2,2,2],res就会变为-1,小于0。为了避免这次不必要的递归,直接在前一次递归,即第3次递归的时候for循环直接跳过2,new变为[2,2,3],就会满足要求
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            output = []     
            candidates.sort()
            def digui(zuhe,candidates, res):
                for index,num in enumerate(candidates):     
                    if res - num < 0:
                        return
                    new = zuhe + [num]
                    if res - num == 0:
                        output.append(new)
                        return
                    if res - num < candidates[0]:
                        continue
                    digui(new,candidates[index:],res-num)
            digui([],candidates, target)  
            return output  

40. 组合总和 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]
]

这道题的要点在于对原始的数组进行了排序,例如对于第一个例子,[1,2,5]是一个答案,如果不排序[2,1,5]也会是一个答案。

这里面涉及三个枝剪条件:

  1. 每当进入新的构成,先考虑该构成的首字符是否和上一个一样,如果一样的话直接跳过,continue
  2. 如果当前的数字num>res,说明后面的数字也不会满足要求,直接return
  3. 如果当前的组合new满足要求,将其添加到output中,则后面的数字也不会满足要求,直接return 
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        output = []
        
        def digui(candidates,lists,res):
            for i,num in enumerate(candidates):
                if i > 0 and candidates[i] == candidates[i-1]:
                    continue
                if res - num < 0:
                    return
                new = lists + [num]
                if res - num == 0:
                    output.append(new)
                    return
                digui(candidates[i+1:],new,res - num)
        digui(candidates,[],target)
        return output

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

相比于上题,本题更为简单。因为组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字,故不需要在排序了。枝剪条件相同。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        output = [] 
        candicate = [i for i in range(1,10)]
        
        def huisu(zuhe,candicate,res):
            for index, num in enumerate(candicate):
                if num > res:  #如果当前的数字num>res,说明后面的数字也不会满足要求,直接return
                    return 
                new = zuhe + [num]
                if res-num == 0 and len(new) == k:     #如果num = res,将目前的组合添加进去
                    output.append(new)                 #与此同时后面的数字也不会满足要求,返回
                    return
                huisu(new,candicate[index+1:],res-num)
                
        huisu([],candicate,n)
        return output

78. 子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。

示例:输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

    def subsets(self, nums: List[int]) -> List[List[int]]:
        output = []   
        output.append([])
        def digui(zuhe,nums):
            if nums == []:
                return
            for index,num in enumerate(nums):   
                new = zuhe + [num]
                if new not in output:
                    output.append(new)
                digui(new,nums[index+1:])

        digui([],nums)  
        return output 

90. 子集 II

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

 因为给定的数组nums可能含有重复元素,因此需要排序

    def subsets2(self, nums):
        output = []   
        nums.sort()
        output.append([])
        def digui(zuhe,candidates):
            if candidates == []:
                return
            for index,num in enumerate(candidates): 
                if index > 0 and candidates[index] == candidates[index-1]:
                    continue
                new = zuhe + [num]
                if new not in output:
                    output.append(new)
                digui(new,candidates[index+1:])

        digui([],candidates)  
        return output 

 

本文地址:https://blog.csdn.net/Mr_health/article/details/107657385