Combination Sum

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

解题思路：

0.前提：默认数组增量排序，lintcode.com 上的测试集出现了降序数组，自己先排序把

1. 定义个Stack，存储已经遍历的元素（可以重复）。

2. 如果计算Stack中的所有元素和，有三种情况：

a. 比target小，继续增加新元素，但是新元素要比我们已经加入的所有值 x 大于或等于 Max(stack)

b. 等于target，保存stack值；将stack 中最后一个元素出栈（stack.pop()），并将剩余的栈顶元素值变大 (x = stack.pop(); new x >x ; stack.push(new x))

c. 大于target，将stack 中最后一个元素出栈（stack.pop()），并将剩余的栈顶元素值变大 (x = stack.pop(); new x >x ; stack.push(new x))

d. stack 为空，计算结束

备注：对比发现b和c的情况类型，代码优化下又省了20行代码。 看了下网上的其他解法，迭代实现肯定是简单，感觉还是自己这个思路更清晰些，三种情况处理完毕OK，该问题麻烦的地方是需要返回满足的LIst结果，如果没有这个结果，无论是迭代还是内部循环，实现都会更简单一些。

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
<span style="white-space:pre">		</span>if (candidates == null || candidates.length == 0)
<span style="white-space:pre">			</span>return new ArrayList<List<Integer>>();


<span style="white-space:pre">		</span>List<List<Integer>> res = new ArrayList<List<Integer>>();


<span style="white-space:pre">		</span>int N = candidates.length;
<span style="white-space:pre">		</span>Stack<Integer> s = new Stack<Integer>();
<span style="white-space:pre">		</span>s.push(0);
<span style="white-space:pre">		</span>int tmp = 0;
<span style="white-space:pre">		</span>while (!s.isEmpty()) {
<span style="white-space:pre">			</span>int i = s.pop();
<span style="white-space:pre">			</span>tmp = tmp + candidates[i];
<span style="white-space:pre">			</span>if (tmp < target) {
<span style="white-space:pre">				</span>s.push(i);
<span style="white-space:pre">				</span>s.push(i);
<span style="white-space:pre">			</span>} else if (tmp >= target) {
<span style="white-space:pre">			</span>    if(tmp == target){
    <span style="white-space:pre">				</span>List<Integer> l = new ArrayList<Integer>();
    <span style="white-space:pre">				</span>List<Integer> t = new ArrayList<Integer>();
    <span style="white-space:pre">				</span>t.addAll(s);
    <span style="white-space:pre">				</span>for (int k : t) {
    <span style="white-space:pre">					</span>l.add(candidates[k]);
    <span style="white-space:pre">				</span>}
    <span style="white-space:pre">				</span>l.add(candidates[i]);
    <span style="white-space:pre">				</span>res.add(l);
                }
                
<span style="white-space:pre">				</span>tmp = tmp - candidates[i];
<span style="white-space:pre">				</span>while (!s.isEmpty()) {
<span style="white-space:pre">					</span>i = s.pop();
<span style="white-space:pre">					</span>tmp = tmp - candidates[i];
<span style="white-space:pre">					</span>i ++;
<span style="white-space:pre">					</span>if(i<N){
<span style="white-space:pre">						</span>s.push(i);
<span style="white-space:pre">					</span>    break;<span style="white-space:pre">	</span>
<span style="white-space:pre">					</span>}
<span style="white-space:pre">				</span>}
<span style="white-space:pre">			</span>} 
<span style="white-space:pre">		</span>}


<span style="white-space:pre">		</span>return res;
<span style="white-space:pre">	</span>}
}