Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Algorithm:

Imagine you have n cards on your hand and each card has a unique number between 1~n. There are k buckets in front of you. You need to drop your cards into the buckets to come up with a combination.

There's only one rule to follow:

Each time you step in front of the ith bucket, you have to increase the number to drop in from last time.

For example, you drop in 1 in the first bucket, next time you step in front of the first bucket, you have to drop in 2.

Say n = 3, k = 2

          

i = 1 : [ 1 ] [ ]      Drop one in the first bucket

i = 2 : [ 1 ] [ 2 ]   => one combination (1, 2)

i = 2 : [ 1 ] [ ]     When the bucket is full, retrieve the card back to your hand

i = 2 : [ 1 ] [ 3 ]   Because you drop in 2 last time, so you drop in 3  => 2nd combination (1, 3)

i = 2 : [ 1 ] [ ]

i = 1 : [ ] [ ]         You can't drop in 4, so step to the first bucket(rest count on i = 2),
                          and retrieve 1 back to your hand

i = 1 : [ 2 ] [ ]      Because you drop in 1 last time at i = 1, so you drop in 2

i = 2 : [ 2 ] [ 1 ]   Since the count were reset, drop in 1 => (2, 1)

i = 2 : [ 2 ] [ ]

i = 2 : [ 2 ] [ 3 ]   Since 2 is not available, drop in 3 => (2, 3)

i = 2 : [ 2 ] [ ]

i = 1 : [ ] [ ]         Reset count for i = 2

i = 1 : [ 3 ] [ 1 ]   => (3, 1)

i = 2 : [ 3 ] [ ]     

i = 2 : [ 3 ] [ 2 ]   => (3, 2)

We notice that the result is actually the permutation of 3 out of 2 elements. So the combination has to divide by k! which is 2 in this case. To achieve the requirement, we have to add one more rule to the algorithm: The number in the bucket has to be bigger than the one in the previous bucket.

Hence, (3, 1), (3, 2) and (2, 1) is not valid

The mathematical calculation for only one rule is Cn_k * k! = n! / (n-k)! = 3! / 1! = 6

The mathematical calculation for two rules is Cn_k = n! / ((n-k)! * k!) = 3! / (2! * 1!) = 3

Solution:

class Solution {
  
    void DFS(int n, int k, int step, List<Integer> ans, List<List<Integer>> res){
      if( ans.size() == k ){
        ArrayList<Integer> temp = new ArrayList<Integer>(ans);
        res.add(temp);
        return;
      }
  
      // Start with step, which implies the 2nd rule
      // i.e. You will get (1,2) but not (2,1)
      // If you want to get all the permutations, you start with i = 1
      for(int i=step; i <= n; i++){
          ans.add(i);
          DFS(n, k, i+1, ans, res);
          ans.remove(ans.size()-1);
      }
      
    }
  
    public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      List<Integer> answer = new ArrayList<Integer>();
      
      DFS(n, k, 1, answer, result);
      
      return result;
        
    }
}

Performance: