Non-Recursive JAVA solution


  • 10
    C
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        int i=0, size = candidates.length, sum=0;
        Stack<Integer> combi = new Stack<>(), indices = new Stack<>();
        List<List<Integer>> result = new ArrayList<>();
        while (i < size) {
        	if (sum + candidates[i]>= target) {
        		if (sum + candidates[i] == target) {
        			combi.push(candidates[i]);
        			result.add(new ArrayList<>(combi));
        			combi.pop();
        		}
        		// indices stack and combination stack should have the same size all the time
        		if (!indices.empty()){
        			sum -= combi.pop();
        			i = indices.pop();
        			while (i == size-1 && !indices.empty()) {
        				i = indices.pop();
        				sum -= combi.pop();
        				
        			}
        		}
        		i++;
        	} else {
        		combi.push(candidates[i]);
        		sum +=candidates[i];
        		indices.push(i);
        	}
        }
        return result;
    }

  • 0
    L

    Thank you to provide such precisely cogged codes which run like a boutique clock.
    And it is really based on backtracking.
    The only pity is the lack of comments to polish those brilliant idea.


  • 0
    Q

    This is a very subtle and concise method,thank you for providing. Could you please apply it into combination sum II, I have tried but I can't, there are a lot of corner cases I can't handle.


  • 0
    S

    @qlan2

    class Solution(object):
      def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort(reverse=True)
        i, s, size = 0, 0, len(candidates)
        indexList, tmpResult, result = [], [], []
        while i < size:
          tmpResult.append(candidates[i])
          indexList.append(i)
          s += candidates[i]
          i += 1
          if s >= target or i == size:
            if s == target:
              result.append(tmpResult[:])
    
            s -= tmpResult.pop()
            i = indexList.pop()+1
            while i == size and tmpResult:
              s -= tmpResult.pop()
              i = indexList.pop() + 1
    
        return result
    

  • 0
    S

    @sunnysuhappy
    sorry this is the right one:

    class Solution(object):
      def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort(reverse=True)
        i, s, size = 0, 0, len(candidates)
        indexList, tmpResult, result = [], [], []
        while i < size:
          tmpResult.append(candidates[i])
          indexList.append(i)
          s += candidates[i]
          i += 1
          if s >= target or i == size:
            if s == target:
              result.append(tmpResult[:])
    
            tmpI = tmpResult.pop()
            s -= tmpI
            i = indexList.pop()+1
    
            while i >= size or tmpI == candidates[i]:
              if i < size:
                i += 1
              else:
                if tmpResult:
                  tmpI = tmpResult.pop()
                  s -= tmpI
                  i = indexList.pop() + 1
                else:
                  break
    
        return result
    

Log in to reply
 

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