Java recursive backtracking clean code


  • 0
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> list = new ArrayList<>();
            combine(list, new ArrayList<>(), n, k);
            return list;
        }
        
        private void combine(List<List<Integer>> list, List<Integer> comb, int n, int k) {
            if (k > n)
                return;
            if (k == 0) {
                list.add(new ArrayList<>(comb));
                return;
            }
            comb.add(0, n); // add to the head of list for ascending order
            combine(list, comb, n - 1, k - 1); // choose n
            comb.remove(0);
            combine(list, comb, n - 1, k); // not choose n
        }
    }

  • 0
    Z

    Hi, my idea is very similar, besides I checked when to not ignore more elements. see below code.

    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);
    }

Log in to reply
 

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