Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 40 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 40 # by problem number
lcpy gen -s combination_sum_ii # by problem name
candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
class Solution:
# Time: O(2^n)
# Space: O(n)
def combination_sum2(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
result: list[list[int]] = []
def backtrack(start: int, remaining: int, path: list[int]) -> None:
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i + 1, remaining - candidates[i], path)
path.pop()
backtrack(0, target, [])
return result
| Time | Space |
|---|---|
| O(2^n) | O(n) |