Problem:
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Solution:
We want to take k numbers out of n numbers, the order doesn't matter. There will be C(n, k) possible combinations. To code it, we need to backtrack.
public void backtrack(int first, LinkedList<Integer> curr) {
// if the combination is done
if (curr.size() == k)
output.add(new LinkedList(curr));
for (int i = first; i < n + 1; ++i) {
// add i into the current combination
curr.add(i);
// use next integers to complete the combination
backtrack(i + 1, curr);
// backtrack
curr.removeLast();
}
}
the reason i start at first instead of 0 is because, we don't want to include duplicate elements, if the order do matter, the code will be
public void backtrack(int first, LinkedList<Integer> curr) {
// if the combination is done
if (curr.size() == k)
output.add(new LinkedList(curr));
for (int i = 1; i < n + 1; ++i) {
// add i into the current combination
if(curr.contains(i)) continue;
curr.add(i);
// use next integers to complete the combination
backtrack(i + 1, curr);
// backtrack
curr.removeLast();
}
}
import java.util.*;
class Solution {
public static void main(String...args) {
List<List<Integer>> result = combine(4, 2);
for(List<Integer> l : result) {
for(Integer i : l) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
List<Integer> nums = new ArrayList<>();
for(int i = 0; i < n; i++) {
nums.add(i+1);
}
backtrack(result, nums, 0, tmp, k);
return result;
}
//1 2 3 4 5 6 7
// .
private static void backtrack(List<List<Integer>> result, List<Integer> nums, int pos, List<Integer> tmp, int k) {
if(k <= 0) {
result.add(new ArrayList(tmp));
return;
}
for(int i = pos; i < nums.size(); i++) {
tmp.add(nums.get(i));
backtrack(result, nums, i+1, tmp, k - 1);
tmp.remove(nums.get(i));
}
}
}
class Solution {
public static void main(String...args) {
List<List<Integer>> result = combine(4, 2);
for(List<Integer> l : result) {
for(Integer i : l) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
List<Integer> nums = new ArrayList<>();
for(int i = 0; i < n; i++) {
nums.add(i+1);
}
backtrack(result, nums, 0, tmp, k);
return result;
}
//1 2 3 4 5 6 7
// .
private static void backtrack(List<List<Integer>> result, List<Integer> nums, int pos, List<Integer> tmp, int k) {
if(k <= 0) {
result.add(new ArrayList(tmp));
return;
}
for(int i = pos; i < nums.size(); i++) {
tmp.add(nums.get(i));
backtrack(result, nums, i+1, tmp, k - 1);
tmp.remove(nums.get(i));
}
}
}
The are C(n, k) combinations, for each combination, we have a have to copy a k sized array, the time complexity is O(kC(n,k)), the space complexity is O(kC(n,k)) too.
