Combinations (LeetCode Backtracking)

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

Idea: Depth-first search. To avoid duplication, start from 1, then only add numbers bigger than all the current numbers to the set until the set size is k. Then collect all the combinations.

Time: O(n!) Space: O(n)

Code:

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     dfs(result,path,1,n,k);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result, List<Integer> path, int start, int end, int k)  
   {  
     if(k==path.size())  
     {  
       result.add(new ArrayList<Integer>(path));  
       return;  
     }  
     for(int i=start;i<=end;i++)  
     {  
       path.add(i);  
       dfs(result,path,i+1,end,k);  
       path.remove(path.size()-1);  
     }  
   }  
 }