Problem Statement:
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 <= 201 <= k <= n
Approach:
- Generate all combinations of
size kfrom numbers 1 to n using recursion. - Start from 1 and explore each number by either including it or skipping it.
Keep adding numbersto the current path until its length becomes k.- When path length is
k, add it to the result. - Backtrack by removing the last added number and try the next one.
Dry Run
Input: n = 4, k = 2
Step 0: Start Function combine(4, 2) Initialize: result = [] path = [] Call backtrack([], 1) Loop i = 1 path.push(1) → path = [1] Call backtrack([1], 2) Loop i = 2 path.push(2) → path = [1, 2] Call backtrack([1, 2], 3) path.length == k → result = [[1, 2]] path.pop() → path = [1] Loop i = 3 path.push(3) → path = [1, 3] Call backtrack([1, 3], 4) path.length == k → result = [[1, 2], [1, 3]] path.pop() → path = [1] Loop i = 4 path.push(4) → path = [1, 4] Call backtrack([1, 4], 5) path.length == k → result = [[1, 2], [1, 3], [1, 4]] path.pop() → path = [1] path.pop() → path = [] Loop i = 2 path.push(2) → path = [2] Call backtrack([2], 3) Loop i = 3 path.push(3) → path = [2, 3] Call backtrack([2, 3], 4) path.length == k → result = [..., [2, 3]] path.pop() → path = [2] Loop i = 4 path.push(4) → path = [2, 4] Call backtrack([2, 4], 5) path.length == k → result = [..., [2, 4]] path.pop() → path = [2] path.pop() → path = [] Loop i = 3 path.push(3) → path = [3] Call backtrack([3], 4) Loop i = 4 path.push(4) → path = [3, 4] Call backtrack([3, 4], 5) path.length == k → result = [..., [3, 4]] path.pop() → path = [3] path.pop() → path = [] Loop i = 4 path.push(4) → path = [4] Call backtrack([4], 5) Loop ends (start > n) path.pop() → path = [] Step 3: End Return result = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Output:
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
var combine = function(n, k) {
let result = [];
let backtrack = (path, start) => {
if(path.length == k) {
result.push([...path]);
return;
}
for(let i = start; i <= n; i++){
path.push(i);
backtrack(path, i+1);
path.pop();
}
}
backtrack([], 1);
return result;
};
def backtrack(n, k, start, path, result):
if len(path) == k:
result.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
backtrack(n, k, i + 1, path, result)
path.pop()
def combine(n, k):
result = []
backtrack(n, k, 1, [], result)
return result
# Example
print(combine(4, 2))
import java.util.*;
public class Main {
static void backtrack(int n, int k, int start, List path, List> result) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= n; i++) {
path.add(i);
backtrack(n, k, i + 1, path, result);
path.remove(path.size() - 1);
}
}
static List> combine(int n, int k) {
List> result = new ArrayList<>();
backtrack(n, k, 1, new ArrayList<>(), result);
return result;
}
public static void main(String[] args) {
List> ans = combine(4, 2);
for (List list : ans) {
System.out.println(list);
}
}
}
void backtrack(int n, int k, int start, vector& path, vector>& result) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
backtrack(n, k, i + 1, path, result);
path.pop_back();
}
}
vector> combine(int n, int k) {
vector> result;
vector path;
backtrack(n, k, 1, path, result);
return result;
}
int main() {
int n = 4, k = 2;
vector> ans = combine(n, k);
for (auto &vec : ans) {
for (int num : vec) cout << num << " ";
cout << "\n";
}
return 0;
}
void backtrack(int n, int k, int start, int path[], int pathSize) {
if (pathSize == k) {
for (int i = 0; i < k; i++) printf("%d ", path[i]);
printf("\n");
return;
}
for (int i = start; i <= n; i++) {
path[pathSize] = i;
backtrack(n, k, i + 1, path, pathSize + 1);
}
}
int main() {
int n = 4, k = 2;
int path[20];
backtrack(n, k, 1, path, 0);
return 0;
}
using System;
using System.Collections.Generic;
class Program {
static void Backtrack(int n, int k, int start, List path, List> result) {
if (path.Count == k) {
result.Add(new List(path));
return;
}
for (int i = start; i <= n; i++) {
path.Add(i);
Backtrack(n, k, i + 1, path, result);
path.RemoveAt(path.Count - 1);
}
}
static List> Combine(int n, int k) {
var result = new List>();
Backtrack(n, k, 1, new List(), result);
return result;
}
static void Main() {
var ans = Combine(4, 2);
foreach (var list in ans) {
Console.WriteLine(string.Join(" ", list));
}
}
}
