Java , recursion different with others


  • 0
    Z

    This program has two scalars to move forward. One is index for cs, and the other one is repeat count for given index.

    Below code uses for loop to increase repeat count and recursion to incerase cur index; however, the other way around also solves this probmem - for loop advance cur idx and recursion increases repeat count.

    I found this way more intuitive.

    public List<List<Integer>> combinationSum(int[] cs, int t) {
        Arrays.sort(cs); 
        
        List<List<Integer>> ret = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        int curIdx = 0;
        
        helper(cs, ret, path, curIdx, t);
        
        return ret;
    }
    
    // idx : current number's idx. it never decreases.
    void helper(int[] cs,List<List<Integer>> ret, LinkedList<Integer> path, int idx, int t ){
        if (t == 0){
            ret.add(new ArrayList<>(path));
            return ;
        }
        else if(idx == cs.length || t < 0){
            return ; // no solution found in current dfs 
        }
        
        // repeat control. from 0 to max possible. 
        for(int i = 0; t - i * cs[idx] >= 0;  i ++){
            for(int j =0 ; j < i; j ++)
                path.add(cs[idx]);
            
            helper(cs, ret, path, idx + 1, t - i * cs[idx] );
            
    
            for(int j =0 ; j < i; j ++) // backtracing
                path.removeLast(); // remove tail
        }
            
    }

Log in to reply
 

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