LeetCodeの配列[Permutations]の組合せ[Combinations]と実現[Python]

8255 ワード

leetcodeには2つの古典的なテーマがあり、1つの配列の配列と組み合わせを求めて、深さ優先再帰検索で解くことができます.一緒に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の後の数に対して全列に再帰します
再帰が完了したら、元の置換位置の2つの数を戻して、次の置換が元の順序に基づいていることに注意してください.
フル配列なので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],
]

考え方:この問題は配列問題と似ている点もあれば、異なる点もあり、すべてのn要素ではなくk要素が必要であるため、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/4332522.html