本文共 1507 字，大约阅读时间需要 5 分钟。

1.回溯法 

参考1.

       2. 

2.leetcode 78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

示例:

输入: nums = [1,2,3]

class Solution:    def subsets(self, nums: List[int]) -> List[List[int]]:        result = []                def dfs(lst ,nums , pos):            # pos是lst的尾巴，用于：之后的数字选择只能在pos之后            result.append(lst[:])#复制lst            for i in range(pos,len(nums)):                lst.append(nums[i])                dfs(lst,nums,i+1)                lst.pop()#为了返回同期的上一层                dfs([],nums,0)        return result

3.leetcode77 组合

给定两个整数 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: int, k: int) -> List[List[int]]:        lst =[]        result = []        def dfs(first,lst):            if len(lst) == k:                result.append(lst[:])            for i in range(first,n+1):                lst.append(i)                dfs(i+1,lst)                lst.pop()        dfs(1,lst)        return result

4 排列问题

[红、黄、蓝、绿]四本书有几种排列方式

思路： solution中通过递归的方法添加完数组中的第一本书；再通过for回溯到原数组，solution添加第二本，再递归

class Solution():    def solveit(self,array):        self.helper(array,[])    def helper(self,array,solution):        if len(array)==0:            print(solution)            return         for i in range(len(array)):            newsolution = solution+[array[i]]            newarray = array[:i]+array[i+1:] #删除第i个            self.helper(newarray,newsolution)

转载地址：http://derii.baihongyu.com/