LeetCode之排列[ Permutations ] 组合[ Combinations ]与实现[ Python ]

「爱情、让人受尽委屈。」 2022-01-26 10:55 172阅读 0赞

leetcode中有两道经典的题目，求一个数组的排列和组合，都可以用深度优先递归搜索的方式来求解，让我们一起来look look。

#### 排列\[ Permutations \] ####

题：Given a collection of **distinct** integers, return all possible permutations.

**Example:**

Input: [1,2,3]
    Output:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

思路：可以把全排列问题进行分解，变成子问题直至可以直接求解。nums = \[1,2,3\]，可以先固定1，然后将 \[2,3\] 进行全排的结果加上1即可，之后再固定2，全排\[1,3\]，依次类推…

下面为对应的代码，固定某个数，即将它放在start位置，再对start之后的数递归全排

要注意的是，在递归完成之后，要将原来调换位置的两个数换回来，使得下一次的调换还是基于原来的顺序

因为它是全排列，所以它的DFS搜索要到n才结束

对于递归，要理解的一个关键点是，递归函数前面的部分是正向运行的，后面的部分是逆向运行的。

class Solution:
        def permute(self, nums):
            res = []
            self.func(nums, 0 ,res)
            return res
    
        def func(self,nums, start, res):
            if start==len(nums):
                res.append(nums.copy())
            else:
                for i in range(start, len(nums)):
                    nums[start], nums[i] = nums[i], nums[start]
                    self.func(nums, start+1, res)
                    nums[start], nums[i] = nums[i], nums[start]

#### 组合\[ Combinations \] ####

题：Given two integers *n* and *k*, return all possible combinations of *k* numbers out of 1 … *n*.

**Example:**

Input: n = 4, k = 2
    Output:
    [
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]

思路：这一题和排列题有相似之处，也有它不一样的地方，它需要k个元素，而不是所有的n个元素，因此它的DFS搜索到k结束。因此他也需要一个额外的temp数组去保存中间结果。

说实话，对于这里，start 的含义我也没有很理解，希望知晓的朋友可以在评论里说明一下，感谢~

class Solution:
        def combine(self, n, k):
            if k>n or k<0:
                return []
            res = []
            temp = []
            self.func(n, k, 1, temp, res)
            return res
    
        def func(self, n, k, start, temp, res):
            if len(temp) == k:
                res.append(temp.copy())
            else:
                for i in range(start, n+1):
                    temp.append(i)
                    self.func(n, k, i+1, temp, res)
                    temp.pop()

参考：

[https://www.cnblogs.com/grandyang/p/4358848.html][https_www.cnblogs.com_grandyang_p_4358848.html]  
[https://www.cnblogs.com/grandyang/p/4332522.html][https_www.cnblogs.com_grandyang_p_4332522.html]

[https_www.cnblogs.com_grandyang_p_4358848.html]: https://www.cnblogs.com/grandyang/p/4358848.html
[https_www.cnblogs.com_grandyang_p_4332522.html]: https://www.cnblogs.com/grandyang/p/4332522.html