Thinking process

Time Complexity

O(C(n, k)) = O(n choose k)

public class Solution { 
    public List<List<Integer>> combine(int n, int k) { 
        List<List<Integer>> res = new ArrayList<>(); 

        dfs(res, new ArrayList<Integer>(), k, n, 1); 

        return res; 
    } 

    private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int k, int n, int start) { 
        if (k == 0) { 
            res.add(new ArrayList<>(list)); 
            return; 
        } 

        for (int i = start; i <= n; i++) { 
            list.add(i); 
            dfs(res, list, k - 1, n, i + 1); 
            list.remove(list.size() - 1); 
        } 
    } 
}