Java easy to read . repeat count controled. (10 ms)


  • 0
    Z
      public List<List<Integer>> combinationSum2(int[] cs, int t) {
            Arrays.sort(cs); 
    
            List<List<Integer>> ret = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            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, List<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.*/
            int count = 0;
            while(idx + count < cs.length && cs[idx] == cs[idx + count])
                count ++;
    
            for(int i = 0;  i <= count ;  i ++){
                int sum = t - i * cs[idx];
                if(sum < 0) // this check saves you 21ms !
                     break;
                    
                for(int j =0 ; j < i; j ++)
                    path.add(cs[idx]);
                // jump to next distinct value
                helper(cs, ret, path, idx + count, sum ); 
    
                for(int j =0 ; j < i; j ++) // backtracing
                    path.remove(path.size()-1); // remove tail
            }
    
        }

Log in to reply
 

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