Given two integers n and k, return all possible combinations of k numbers out of 1…n.
Example:
Input: n = 4, k = 2.
Output: [
[1,2,3],
[1,2,4],
[1,3,4],
[2,3,4]
]
Solution:
This problem is efficiently solved by backtracking algorithm. Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
By using the above technique, we implement our algorithm.
From the starting integer i.e. 1 we generate an array of combinations of integers untill we reach the length of an array, k = 2. we generate every possible solutions, if it’s giving us the required combination, we will add it to the answer array.
After going through every possible combinations and adding it to the array, we will simply return the answer array.
Implementation
Java
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
backtracking(k, 0, nums, new ArrayList(), result);
return result;
}
void backtracking(int k, int start, int[] nums, List<Integer> curr, List<List<Integer>> result) {
if (curr.size() == k) {
result.add(new ArrayList(curr));
} else if (curr.size() < k) {
for (int i = start; i < nums.length; i++) {
curr.add(nums[i]);
backtracking(k, i + 1, nums, curr, result);
curr.remove(curr.size() - 1);
}
}
}
}
Complexity Analysis:
Time Complexity: O(kCkn).
Space Complexity: O(kCkn).
