Please help me apply this subtle iterative method(thx @peike) of combination sum into combi sum II


  • 0
    Q
    //iterative
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Stack<Integer> combi = new Stack<>(), idx = new Stack<>();
        int i = 0, sum = 0, len = num.length;
        while(i < len){
            if(sum + num[i] < target){
                combi.push(num[i]);
                sum += num[i];
                idx.push(i);
            }else{
                if(sum + num[i] == target){
                    combi.push(num[i]);
                    res.add(new ArrayList<Integer>(combi));
                    combi.pop();
                }
                //the size of combi and idx should be the same
                if(!idx.isEmpty()){
                    sum -= combi.pop();
                    i = idx.pop();
                    while(i == len - 1 && !idx.isEmpty()){
                        i = idx.pop();
                        sum -= combi.pop();
                    }
                }
                i++;
            }
        }
        return res;

  • 0
    D

    I also tried to adapt @peike 's combination sum into combi sum II. I use hashset to avoid duplicated solutions.
    I'm new to coding. I would really appreciate it if any of you can help me improve my code. Thanks.

     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
                List<List<Integer>> list = new ArrayList<List<Integer>>();
                if(candidates == null || candidates.length==0)
                return list;
                Arrays.sort(candidates);
                //index of candidates
                int i = 0, size = candidates.length, sum = 0;
                
                //stack for numbers so they can be added to list
                Stack<Integer> item = new Stack<>();
                //stack to track index
                Stack<Integer> indices = new Stack<>();
                //hashset guarantees unique result since duplicate element is alloweded
                HashSet<ArrayList<Integer>> pool = new HashSet<ArrayList<Integer>>(); 
         
                while(i<size) {
                    if (sum + candidates[i] >= target) {
                        if (sum + candidates[i] == target) {
                            item.push(candidates[i]);
                            pool.add(new ArrayList<>(item));
                            item.pop();
                        }
                        //if it is over sum then we need to use new number by increase index
                        if(!indices.isEmpty()) {
                            sum -= item.pop();
                            i = indices.pop();
                        }
                        i++;
                    } else { 
                        //if sum is still less than target after adding last element,
                        //pop previous element and move on to next available element
                        if (i == size-1) {
                    		if (item.isEmpty()) break;
                    		else {
                    			sum -= item.pop();
                    			i = indices.pop()+1;
                    		}
                    	}
                    	//this means no element available, it will go to above lines keeps poping stack
                    	if (i == size-1) 
                    		continue;
                        item.push(candidates[i]);
                        sum += candidates[i];
                        indices.push(i);
                        i++;
                    }
                }
                return new ArrayList<List<Integer>>(pool);
            }

  • 0
    Q

    Your answer is good, I have modified your solution without using hashset.


  • 0
    Q

    The code is as follows:


  • 2
    Q
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] num, int target) {
            if(num == null || num.length == 0) return new ArrayList<List<Integer>>();
            Arrays.sort(num); 
            //items store the elements in the num and indices store index of the corresponding element 
            Stack<Integer> items = new Stack<>();
            Stack<Integer> indices = new Stack<>();
            ArrayList<List<Integer>> res = new ArrayList<>();
            int idx = 0, sum = 0;
            while(idx < num.length){
                if(sum + num[idx] >= target){
                    if(sum + num[idx] == target){
                        items.push(num[idx]);
                        res.add(new ArrayList<Integer>(items));
                        items.pop();
                    }
                    if(indices.isEmpty()) break;
                    sum -= items.pop();
                    idx = indices.pop() + 1;
                    //handle the same value elements
                    while(idx > num.length - 1 || num[idx] == num[idx - 1]){
                        if(idx > num.length - 1){
                            if(indices.isEmpty()) break;
                            idx = indices.pop() + 1;
                            sum -= items.pop();
                        }else if(num[idx] == num[idx - 1]){
                            idx++;
                        }
                    }
                }else{
                    if(idx == num.length - 1){
                        if(indices.isEmpty()) break;
                        idx = indices.pop() + 1;
                        sum -= items.pop();
                        while(idx > num.length - 1 || num[idx] == num[idx - 1]){
                            if(idx > num.length - 1){
                                if(indices.isEmpty()) break;
                                idx = indices.pop() + 1;
                                sum -= items.pop();
                            }else if(num[idx] == num[idx - 1]){
                                idx++;
                            }
                        }
                    }else{
                        items.push(num[idx]);
                        sum += num[idx];
                        indices.push(idx++);
                    }
                }
            }
            return res;
        }
    }

  • 0
    J

    And I've rewritten your new code :P (C++)

    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int> &num, int target) {
            vector<int> numbers = num;  // Why not? This algorithm cost only 16ms for all tests.
            sort(numbers.begin(), numbers.end());
            vector<vector<int>> result;
            vector<int> subset;
            vector<int> stack;
            int i = 0;
            while (i < numbers.size()) {
                if (target - numbers[i] == 0) {
                    result.push_back(subset);
                    result.back().push_back(numbers[i]);
                }
                if (target - numbers[i] <= 0 ||
                        (target - numbers[i] > 0 && i == numbers.size() - 1) ||
                        (target > numbers.back() * (numbers.size() - i))) {
                    if (stack.empty()) return result;
                    target += subset.back();
                    subset.pop_back();
                    i = stack.back() + 1;
                    stack.pop_back();
                    // avoid duplicates
                    while (i >= numbers.size() || (i > 0 && numbers[i-1] == numbers[i])) {
                        if (i >= numbers.size()) {
                            if (stack.empty()) return result;
                            target += subset.back();
                            subset.pop_back();
                            i = stack.back() + 1;
                            stack.pop_back();
                        } else {
                            i++;
                        }
                    }
                } else {
                    subset.push_back(numbers[i]);
                    target -= numbers[i];
                    stack.push_back(i);
                    i++;
                }
            }
            return result;
        }
    };

Log in to reply
 

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