[LeetCode] 0040. 組み合わせ和Ⅱ

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

候補番号のコレクションが与えられると (候補者) と目標数値 (ターゲット)、すべての一意の組み合わせを見つけます。 候補者 ここで、候補数の合計は次のようになります ターゲット.

内の各数字 候補者 のみ使用できます一度組み合わせで。

注記： ソリューションセットには重複した組み合わせが含まれていてはなりません。

例 1:

入力： 候補 = [10,1,2,7,6,1,5]、ターゲット = 8
出力： 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

例 2:

入力： 候補 = [2,5,2,1,2]、ターゲット = 5
出力： 
[
[1,2,2],
[5]
]

制約:

1 <= 候補.長さ <= 100
1 <= 候補者[i] <= 50
1 <= ターゲット <= 30

パイソン

				
					# 時間計算量: O(2^n) # 空間計算量: import リスト クラスの入力による O(n) 解: def comboSum2(self, 候補: List[int], target: int) -> List[List[int]] : 答え = [] 候補者.sort() self.backtrack(候補者, ターゲット, 0, [], 答え) 答えを返す def backtrack(self, 候補者, ターゲット: int, totalIdx: int, パス: List[int], 答え: List[int]): if target < 0: return if target == 0: Answer.append(path) return for i in range(totalIdx, len(candidates)): if i > totalIdx and Candidates[i] ==候補者[i - 1]: 続行 self.backtrack( 候補者, ターゲット - 候補者[i], i + 1, パス + [候補者[i]], 答え, ) 候補者 = [10, 1, 2, 7, 6, 1, 5] ターゲット = 8 print(Solution().combinationSum2(候補, ターゲット))

中くらい

パイソン

関連記事