LeetCode: Combinations

Question:

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],
]

Difficulty: ★★★

Key Word: combination

Reference: http://blog.csdn.net/u010500263/article/details/18435495

---

Thoughts:

This problem is similar to permutation problem.

I used iteration and recursive method to build each combination. For detailed explanation, please read through the reference link.

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if (n<=0||k<=0){
            return null;
        }
        
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        
        int st=1;
        int num=0;
        ArrayList<Integer> subResult=new ArrayList<Integer>();
        buildResult(st, num, k, n, subResult, result);
        
        return result;
    }
    
    private void buildResult(int start, int currentNum, int k, int n, ArrayList<Integer> subResult, ArrayList<ArrayList<Integer>> result)
    {
        if (currentNum==k){
            ArrayList<Integer> temp=new ArrayList<Integer>(subResult);
            result.add(temp);
            return;
        }
        
        for (int i=start; i<=n; i++){
            subResult.add(i);
            buildResult(i+1, currentNum+1, k, n, subResult, result);
            subResult.remove(subResult.size()-1);
        }
    }
}

Complexity Analysis

When k == n, worst case complexity is O((n+k)!)