Description:
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.
Examples:
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.Solution in Python:
To solve the problem of generating all possible combinations of k numbers chosen from the range [1, n], we can use backtracking. Backtracking is an algorithmic technique for solving recursive problems by trying to build a solution incrementally, removing those solutions that fail to satisfy the constraints at any point in time.
Approach:
- Initialize Variables:
- A list
resto store the final combinations. - A temporary list
combto store the current combination.
- A list
- Backtracking Function:
- This function will recursively build the combinations.
- If the current combination
combhaskelements, add it tores. - Otherwise, iterate through the range starting from the current number to
nand try to include the current number in the combination. - After including a number, recursively call the backtracking function with the next number.
- Remove the last number to backtrack and try the next possibility.
- Base and Recursive Case:
- Base case: If the combination length equals
k, add it to the result. - Recursive case: Iterate through the range and build the combination.
- Base case: If the combination length equals
Python
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start, comb):
# If the combination is done
if len(comb) == k:
res.append(comb[:])
return
# Iterate over the range
for i in range(start, n + 1):
# Add i into the current combination
comb.append(i)
# Use next integers to complete the combination
backtrack(i + 1, comb)
# Backtrack by removing the last element
comb.pop()
res = []
backtrack(1, [])
return resExplanation:
- Function
combine:- This is the main function that initializes the result list
resand starts the backtracking process.
- This is the main function that initializes the result list
- Function
backtrack:- Parameters:
start: The current starting number for the combination.comb: The current combination being built.
- If the length of
combequalsk, it means we have a valid combination, so we append a copy of it tores. - Iterate from
startton. For each numberi:- Add
ito the current combinationcomb. - Call
backtrackrecursively withi + 1as the new start to continue building the combination. - After returning from the recursive call, remove
ifromcombto backtrack.
- Add
- Parameters:
- Base Case:
- When
len(comb) == k, a valid combination is found and added tores.
- When
- Recursive Case:
- Loop through numbers from
startton, add each number to the current combination, recursively callbacktrack, and then backtrack by removing the number.
- Loop through numbers from
This algorithm ensures all combinations are generated and is efficient for the given constraints (1 <= n <= 20).
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
// Initialize the result array to store all combinations
let res = [];
// Backtracking helper function
function backtrack(start, comb) {
// If the combination is done (i.e., length of comb is k)
if (comb.length === k) {
// Make a copy of comb and add it to the result
res.push([...comb]);
return;
}
// Iterate over the range from start to n
for (let i = start; i <= n; i++) {
// Add i into the current combination
comb.push(i);
// Use next integers to complete the combination
backtrack(i + 1, comb);
// Backtrack by removing the last element
comb.pop();
}
}
// Start the backtracking with 1 and an empty combination
backtrack(1, []);
// Return the result containing all combinations
return res;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(1, n, k, new ArrayList<>(), res);
return res;
}
private void backtrack(int start, int n, int k, List<Integer> comb, List<List<Integer>> res) {
// If the combination is done
if (comb.size() == k) {
// Make a copy of comb and add it to the result
res.add(new ArrayList<>(comb));
return;
}
// Iterate over the range from start to n
for (int i = start; i <= n; i++) {
// Add i into the current combination
comb.add(i);
// Use next integers to complete the combination
backtrack(i + 1, n, k, comb, res);
// Backtrack by removing the last element
comb.remove(comb.size() - 1);
}
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Combine(int n, int k) {
IList<IList<int>> res = new List<IList<int>>();
Backtrack(1, n, k, new List<int>(), res);
return res;
}
private void Backtrack(int start, int n, int k, List<int> comb, IList<IList<int>> res) {
// If the combination is done
if (comb.Count == k) {
// Make a copy of comb and add it to the result
res.Add(new List<int>(comb));
return;
}
// Iterate over the range from start to n
for (int i = start; i <= n; i++) {
// Add i into the current combination
comb.Add(i);
// Use next integers to complete the combination
Backtrack(i + 1, n, k, comb, res);
// Backtrack by removing the last element
comb.RemoveAt(comb.Count - 1);
}
}
}