【LeetCode】77. Combinations 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python,ライブラリ
2. 解答2:Python,DFS(深さ優先探索)
メモ・参考・感想

問題

原文

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

1
2
3
4

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.

1
2
3

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

1 <= n <= 20

1 <= k <= n

内容

2つの整数n,kが与えられます。

1～nまでの数字で考えらられる全ての組み合わせを返してください。

解答はどの順番でも問題ありません。

※[1,2]、[2,1]のように順番が異なるだけの組み合わせは同じものとしてカウントされます。

※正しくない可能性があります。

解答

解答1：Python,ライブラリ

from itertools import combinations

class Solution:
    def combine(self, n, k):
        answer = list(combinations(range(1, n+1), k))
        return answer

from itertools import combinations

class Solution:

def combine(self, n, k):

answer = list(combinations(range(1, n+1), k))

return answer

Pythonには今回実装するCombinationsの機能を持つライブラリがあるので、

それを使うと簡単に解答ができる。

ただ、今回はその中身を考える問題だと思うのでこれは意味がない。

解答2:Python,DFS(深さ優先探索)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer, element = [], []
        self.DFS(range(1, n+1), k, element,answer)
        return  answer

    def DFS(self, nums, k, element,answer):        
        if len(element) == k:
            answer.append(element)
            return 
        else:
            for i in range(len(nums)):
                self.DFS(nums[i+1:], k, element+[nums[i]], answer)

class Solution:

def combine(self, n: int, k: int) -> List[List[int]]:

answer, element = [], []

self.DFS(range(1, n+1), k, element,answer)

return answer

def DFS(self, nums, k, element,answer):

if len(element) == k:

answer.append(element)

return

else:

for i in range(len(nums)):

self.DFS(nums[i+1:], k, element+[nums[i]], answer)

answerは今回の問題の解答であるリスト。

elementはanswerの各要素。DFS関数により作成・追加される。

numsは組み合わせを作る1~nまでのリスト

kはelementの要素数(1つの組み合わせの要素数)

→k=1なら[1],[2]、k=2なら[1,2],[1,3]、k=3なら[1,2,3],[1,3,2]

DFS関数はelementの作成のために再帰的に呼び出される。

1~nまでの以下の処理をforループで行う。

・1~nまでのループの各回で、numsからi番目の要素を削除してDFSを再帰的に呼び出す。

・elementは最初は空だが、DFSの呼び出しの都度、numsのi番目をelementに追加していく。これにより、elementの要素数はだんだんとk個にまで近づく。

elementの要素数がkと一致したらanswerにelementを追加する。

メモ・参考・感想

・感想

再帰関数を使った問題は実装はおろか理解することがまず難しい。

前：617. Merge Two Binary Trees

次：46. Permutations

LeetCode 解答・解説記事一覧