[leetcode 39. 组合总和] 排序 + 栈

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。
  示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

基本思路

• 排序，假设为顺序。索引从队尾开始
• target > current, 目标大于当前值，索引入栈
• target == 0, 目标值等于0，解题成功。此时栈顶弹出，目标值恢复上一次状态，索引递减，寻找下一个可能的解
• target < current, 索引递减
• 索引溢出，本次结束，栈顶弹出，目标值恢复上一次状态，索引递减

代码

var combinationSum = function(candidates, target) {
    candidates.sort();
    let ret = [],stack = [], i = candidates.length-1;
    while (i>=0 || stack.length>0) {
        if (target == 0) {
            // resolved
            let solution = [];
            for (var k in stack) {
                solution.push(candidates[stack[k]]);
            }
            ret.push(solution);
            target+=candidates[i];
            i = stack.pop() - 1;
        } else if (i < 0) {
            i = stack.pop();
            target+=candidates[i];
            i--;
        } else if (target < candidates[i]) {
            i--;
        } else {
            stack.push(i);
            target -= candidates[i];
        }
    }
    return ret;
};