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.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 20
1 <= k <= n
This problem asks us to find all possible combinations of k numbers chosen from the range [1, n]. The solution uses backtracking, a recursive approach to explore all possible combinations. Two variations of the backtracking approach are presented.
This approach considers each number from 1 to n. For each number, we have two choices: either include it in the current combination or exclude it. This leads to a recursive branching process.
Algorithm:
dfs(i)
function: This recursive function takes an integer i
as input, representing the starting index for the next number to consider.t
) equals k, we've found a valid combination, so we add it to the result (ans
) and return.i
exceeds n, we've exhausted all numbers, so we return.i
to the current combination (t
), recursively call dfs(i + 1)
to explore combinations starting from the next number, and then remove i
from t
(backtracking).dfs(i + 1)
without adding i
to t
, exploring combinations that don't include i
.Code (Python):
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(i: int):
if len(t) == k:
ans.append(t[:]) # Append a copy to avoid modification
return
if i > n:
return
t.append(i)
dfs(i + 1)
t.pop()
dfs(i + 1)
ans = []
t = []
dfs(1)
return ans
Time Complexity: O(k * C(n, k)), where C(n, k) is the number of combinations (n choose k). The algorithm explores all combinations, and for each combination, we spend O(k) time to copy it into the result.
Space Complexity: O(k) due to the recursion depth and the t
list storing the current combination. The space for ans
is O(C(n, k) * k) in the worst case, but this is usually considered separately from the algorithm's space complexity.
This approach is similar to Approach 1 but slightly more efficient because it avoids the redundant recursive calls. Instead of two recursive calls for each number (include/exclude), it iterates through the possible numbers to include in the combination.
Algorithm:
dfs(i)
function: This recursive function takes an integer i
as input, representing the starting index for the next number to consider.i
to n
. For each number j
, it adds j
to the current combination (t
), recursively calls dfs(j + 1)
to explore further combinations, and then removes j
from t
(backtracking).Code (Python):
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(i: int):
if len(t) == k:
ans.append(t[:])
return
if i > n:
return
for j in range(i, n + 1):
t.append(j)
dfs(j + 1)
t.pop()
ans = []
t = []
dfs(1)
return ans
Time Complexity: O(k * C(n, k)). The analysis is the same as in Approach 1.
Space Complexity: O(k), same as Approach 1.
Both approaches have the same time complexity. Approach 2 might be slightly more efficient in practice due to reduced function calls, but the difference is often negligible. The choice between the two approaches is largely a matter of preference and coding style. Other languages follow similar logic and complexity.