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.
Why Backtracking here?
1234
Fix 1: 1
Add 2: <1,2>
Remove 2, Add 3: <1,3> //This remove part is Backtracking
Remove 3, Add 4: <1,4>
Fix 2: 2
Add 3: <1,3>
Remove 3, Add 4: <1,4>
Fix 3: 3
Add 4: <1,4>
O(n!/(n-k)!k!)
4!/2!2! = 6
Because loop only runs 6 times for 4C2 case. Space
vector arr will always be of size k
Again=6 ie O(n!/(n-k)!k!) because 6 function stacks are created in all.
using vecI = vector>;
class Solution {
vecI out;
int n;
int k;
public:
void backtrack(int start, vector& cand_set){
if(cand_set.size() == k){ //Base case
out.push_back(cand_set);
return;
}
for (int i=start; i<=n; ++i) { //Iterate through all candidates
cand_set.push_back(i); //Place candidate
backtrack(i+1, cand_set); //Backtrack
cand_set.pop_back(); //remove this candidate
}
}
vecI combine(int n1, int k1) {
n = n1;
k = k1;
int start = 1;
vector cand_set = {};
backtrack(start, cand_set);
return out;
}
};
class Solution:
def __init__(self):
self.n = 0
self.k = 0
self.out = [[]]
def bt(self, start: int, cand_set: List[int]):
if len(cand_set) == self.k:
self.out.append(cand_set.copy())
return
for i in range(start, self.n+1):
cand_set.append(i)
self.bt(i+1, cand_set)
cand_set.pop()
def combine(self, n1: int, k1: int) -> List[List[int]]:
self.n = n1
self.k = k1
cand_set = []
start = 1
self.bt (start, cand_set)
# out = [[],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
# Return from index 1 to end
return self.out[1:]