【LeetCode】216. Combination Sum III 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, backtrack
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- backtrack

詳細

問題

原文

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.

Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.

1
2
3
4
5

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.

1
2
3
4
5
6
7

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

1
2
3
4

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9

1 <= n <= 60

内容(和訳)

以下の条件を満たす、合計がnになるk個の数のすべての有効な組み合わせを見つけてください。

1から9までの数値のみを使用します。
各数値は最大1回使用されます。

すべての可能な有効な組み合わせのリストを返してください。リストには同じ組み合わせが2回含まれていてはならず、組み合わせは任意の順序で返されても構いません。

※ChatGPTによる翻訳

解答

解答1：Python, backtrack

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        #解答用のリスト
        ret = []
        #dfsメソッドを呼び出す
        self.dfs(list(range(1,10)), k, n, [], ret)
        #解答を返す
        return ret
    #numsは1～9の範囲。ただし、1回しか使えないので再帰呼び出し時は今回使った数字は除外される
    #kは再帰呼び出しの度に1減らされる。再帰呼び出しのたびに1つ数字を使うので、使った数字の分だけ減らされる
    #　0未満になったらもう新しい数字は使えないので条件に当てはまらず、再帰呼び出しの条件から外れる
    #nは数字の合計。使用した数字の値が再帰呼び出しのたびに減らされる。
    #　0未満になったら、数字の合計がnの値を越えることになるため条件に当てはまらず、再帰呼び出しの条件から外れる
    #pathは数字の組み合わせを持つリスト。リスト同士の結合のため、再帰呼び出しのたびにpath+[nums[i]]となる
    #retは解答用の引数
    def dfs(self, nums, k, n, path, ret):
        #kが0未満か、nが0未満ならNoneを返す
        if k<0 or n<0:
            return None
        #問題の条件に当てはまった場合なので、pathをretに加える
        if k==0 and n == 0:
            ret.append(path)
        #条件に当てはまるか、外れるまで1～9までを順に走査し、再帰呼び出し
        for i in range(len(nums)):
            #numsは1→9の順に呼び出すので、次回呼び出し時はnums[i+1:]で2つ目以降の数字だけで良い
            #kは今回の再帰呼び出しで1つ数字を使ったので、残り使える数字はk-1となる
            #nは今回の再帰呼び出しでnums[i]を使ったので、合計してnになるには、n-nums[i]となる
            #pathは、今回の再帰呼び出しで使ったnums[i]をリスト同士で結合する。
            self.dfs(nums[i+1:], k-1, n-nums[i], path+[nums[i]], ret)
            #print(nums[i],"nums[i]")
            #print(path,"path")
            #print(ret,"ret")

class Solution:

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

#解答用のリスト

ret = []

#dfsメソッドを呼び出す

self.dfs(list(range(1,10)), k, n, [], ret)

#解答を返す

return ret

#numsは1～9の範囲。ただし、1回しか使えないので再帰呼び出し時は今回使った数字は除外される

#kは再帰呼び出しの度に1減らされる。再帰呼び出しのたびに1つ数字を使うので、使った数字の分だけ減らされる

#　0未満になったらもう新しい数字は使えないので条件に当てはまらず、再帰呼び出しの条件から外れる

#nは数字の合計。使用した数字の値が再帰呼び出しのたびに減らされる。

#　0未満になったら、数字の合計がnの値を越えることになるため条件に当てはまらず、再帰呼び出しの条件から外れる

#pathは数字の組み合わせを持つリスト。リスト同士の結合のため、再帰呼び出しのたびにpath+[nums[i]]となる

#retは解答用の引数

def dfs(self, nums, k, n, path, ret):

#kが0未満か、nが0未満ならNoneを返す

if k<0 or n<0:

return None

#問題の条件に当てはまった場合なので、pathをretに加える

if k==0 and n == 0:

ret.append(path)

#条件に当てはまるか、外れるまで1～9までを順に走査し、再帰呼び出し

for i in range(len(nums)):

#numsは1→9の順に呼び出すので、次回呼び出し時はnums[i+1:]で2つ目以降の数字だけで良い

#kは今回の再帰呼び出しで1つ数字を使ったので、残り使える数字はk-1となる

#nは今回の再帰呼び出しでnums[i]を使ったので、合計してnになるには、n-nums[i]となる

#pathは、今回の再帰呼び出しで使ったnums[i]をリスト同士で結合する。

self.dfs(nums[i+1:], k-1, n-nums[i], path+[nums[i]], ret)

#print(nums[i],"nums[i]")

#print(path,"path")

#print(ret,"ret")

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：841. Keys and Rooms

次：

LeetCode 解答・解説記事一覧