Find all valid combinations of k
numbers that sum up to n
such that the following conditions are true:
1
through 9
are used.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.
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.
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.
Constraints:
2 <= k <= 9
1 <= n <= 60
Find all unique combinations of k
numbers from 1 to 9 that sum up to n
. Each number can be used at most once.
This problem can be efficiently solved using backtracking with pruning. The backtracking approach explores all possible combinations by recursively adding numbers to a current combination. Pruning helps to avoid unnecessary computations by eliminating branches that cannot lead to a valid solution.
dfs(index, currentSum, combination)
: This recursive function explores combinations starting from index
.
currentSum
equals n
and the length of combination
is k
, a valid combination is found. Add it to the result and return.currentSum
exceeds n
or the length of combination
exceeds k
, this branch cannot lead to a valid solution. Return.index
to 9 (inclusive). For each number i
:
i
to the combination
.dfs(i + 1, currentSum + i, combination)
. i + 1
ensures that each number is used at most once.i
from the combination
(backtracking).Main Function: Initialize an empty result list and call dfs(1, 0, [])
to start the search.
def combinationSum3(k, n):
"""
Finds all valid combinations of k numbers that sum up to n.
Args:
k: The number of elements in each combination.
n: The target sum.
Returns:
A list of lists, where each inner list represents a valid combination.
"""
result = []
def dfs(index, current_sum, combination):
if current_sum == n and len(combination) == k:
result.append(combination.copy()) # Add a copy to avoid modification
return
if current_sum > n or len(combination) > k:
return
for i in range(index, 10): # Iterate from index to 9
combination.append(i)
dfs(i + 1, current_sum + i, combination) # Explore next number
combination.pop() # Backtrack
dfs(1, 0, [])
return result
combination
list).A more concise solution can be achieved using bit manipulation. Each bit in a 9-bit integer represents the inclusion (1) or exclusion (0) of a number from 1 to 9.
k
.n
, add the combination to the result.def combinationSum3_bit(k, n):
result = []
for i in range(1 << 9): # Iterate through all 9-bit integers
combination = []
count = 0
total = 0
for j in range(9):
if (i >> j) & 1: # Check if j-th bit is set
count += 1
total += j + 1
combination.append(j + 1)
if count == k and total == n:
result.append(combination)
return result
k
.Both solutions correctly solve the problem. The backtracking approach is generally more flexible and can be adapted to similar problems with different constraints more easily. The bit manipulation approach is more concise but is less intuitive and efficient only for specific problems like this where numbers are in a small, fixed range.