Non recursive java solution


  • 0
    G
    public class Solution {
        private int[] mul;
        private int pos;
        private int rest;
        private int[] candidates;
        int l;
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            this.candidates = candidates;
            l = 0;
            for (;l<candidates.length; l++)
                if(candidates[l]>target)
                    break;
                
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            mul = new int[l];
            pos=-1;
            rest=target;
            do{
                if (try_comb())
                    add_comb(res);
            }while(get_next_comb());
                    
            return res;
        }
        
        private boolean try_comb(){
            while(rest>0 && ++pos<l){
                int n = rest / candidates[pos];
                mul[pos] = n;
                rest -= n*candidates[pos];
                if (rest==0)
                    return true;
            }
            pos--;
            return false;
        }
        
        private void add_comb(List<List<Integer>> res){
            ArrayList<Integer> nl = new ArrayList<Integer>();
            for(int i=0; i<l; i++)
                for(int j=0; j<mul[i]; j++)
                    nl.add(candidates[i]);
            res.add(nl);
        }
        
        private boolean get_next_comb(){
            while (pos>=0){
                if(mul[pos]>0){
                    mul[pos]--;
                    rest+=candidates[pos];
                    return true;
                }
                else{
                    pos--;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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