Combinations

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,

  1. Within every entry, elements should be sorted. [1, 4] is a valid entry while [4, 1] is not.
  2. 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);
        }
    }
}