Java, DFS + backtracking , easy to read. fast. (2 ms)

  • 0
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        helper(n, 1, k, ret, path);
        return ret;
    // recursively pick elements into combination path. DFS + backtracking
    void helper(int n, int cur, int k, List<List<Integer>> ret, List<Integer>path){
        if(k == 0){
            ret.add(new ArrayList<>(path));
            return ;
        /*pick cur.*/
        helper(n, cur + 1, k -1 ,ret,path);
        if(n-cur +1 == k) // pick every element from cur and beyond.
        /*ignore cur*/
        helper(n, cur + 1, k , ret,path);

    Brief explanation: basic idea is - only two options available at a certain element: pick it OR ignore it.
    But at some point, when certain number of previous elements ignored, no more should be ignored (e.g. n = 3, k =2, in this case if 1 is ignored, 2 and 3 must be selected).

    Please see the code for corresponding pars.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.