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


  • 0
    Z
    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.*/
        path.add(cur);
        helper(n, cur + 1, k -1 ,ret,path);
        path.remove(path.size()-1);
        
        if(n-cur +1 == k) // pick every element from cur and beyond.
            return;    
        
        /*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.