Given two integers n and k, return all possible combinations of k numbers out of 1 2 3 ... n.
Make sure the combinations are sorted.
To elaborate,
Within every entry, elements should be sorted. [1, 4] is a valid entry while [4, 1] is not.
Entries should be sorted within themselves.
Example : If n = 4 and k = 2, a solution is:
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4],
]
Method:
For a list for 1..n, and for a recursion level of k, in each level, add a number and then go to next level.
Solution:
Time: O(n^k) Space: O(n^k)
public class Solution { public ArrayList<ArrayList<Integer>> combine(int A, int B) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (A < B) return result; ArrayList<Integer> current = new ArrayList<>(); helper(result, current, 0, A, B); return result; }
private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current, int val, int A, int B) { if (current.size() == B) { result.add(new ArrayList<>(current)); return; } for (int i = val + 1; i <= A; i ++) { current.add(i); helper(result, current, i, A, B); current.remove(current.size() - 1); } } }