现在的位置: 首页 > 综合 > 正文

Combination Sum

2018年05月13日 ⁄ 综合 ⁄ 共 4236字 ⁄ 字号 评论关闭

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where
the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.


For example, given candidate set 2,3,6,7 and target 7

A solution set is: 
[7] 
[2, 2, 3] 

注意

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1a2,
    … , 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);
		if (candidates == null || candidates.length == 0)
			return new ArrayList<List<Integer>>();

		List<List<Integer>> res = new ArrayList<List<Integer>>();

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

		return res;
	}
}

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in Cwhere the candidate numbers
sums to T.

Each number in C may only be used once in the combination.

注意

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

For example, given candidate set 10,1,6,7,2,1,5 and target 8,

A solution set is: 

[1,7]

[1,2,5]

[2,6]

[1,1,6]

解题思路:上一题的变体,使用上面的解法也可以求解。这里我借鉴网上使用NP问题的求解方式,使用迭代求解,但是网上迭代程序感觉有些重复计算了。想要避免重复计算,还是先对数组排序,这样每次新加入的元素,进行递增计算,保存满足条件的集合。

PS : 这里代码要少上10行,程序的思路也更加明显,容易出错的地方是要对新的迭代计算参数定位好。
public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] num, int target) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (num != null && num.length == 0)
			return res;
		Arrays.sort(num);
		find(num, target, res, new ArrayList<Integer>());
		return res;
	}

	void find(int[] num, int target, List<List<Integer>> res, List<Integer> path) {
		for (int i = 0; i < num.length; i++) {
		    if(i>=1 && num[i]== num[i-1])
		        continue;
			int tmp = target - num[i];
			if (tmp > 0 && num.length > i) {
				int[] num2 = new int[num.length - 1];
				System.arraycopy(num, i+1, num2, 0, num.length - 1 - i);
				List<Integer> path2 = new ArrayList<Integer>();
				path2.addAll(path);
				path2.add(num[i]);
				find(num2, tmp, res, path2);
			} else {
				if (tmp == 0) {
					List<Integer> path2 = new ArrayList<Integer>();
					path2.addAll(path);
					path2.add(num[i]);
					res.add(path2);
				}
				// tmp <= 0
				break;
			}
		}
	}
}

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

样例

For example,

If n = 4 and k = 2, a solution is:

[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
本题没想到什么解题技巧,首先用栈实现程序,感觉程序看起来还是比较繁琐,参考网上的解法,实现下面程序。
通过一个数组来存储需要检验的数据,然后通过一个游标 start变量来动态控制数组里的值,函数递归的时候,start ++,函数返回的时候,将数组A[start]位重置后,设入新值,开始新的递归,直到递归结束。
public class Solution {
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    public List<List<Integer>> combine(int n, int k) {
		if (n <= 0 || k <= 0 || k > n)
			return new ArrayList<List<Integer>>();

		List<List<Integer>> res = new ArrayList<List<Integer>>();
		int[] A = new int[k];
		find(A, n, 0, res);

		return res;
	}

	void find(int[] A, int n, int start, List<List<Integer>> res) {
		if (start == A.length) {
			List<Integer> l = new ArrayList<Integer>();
			for (int b : A)
				l.add(b);
			res.add(l);
			return;
		}

		int max = 0;
		for (int i = 0; i < A.length; i++)
			if (max < A[i])
				max = A[i];
		for (int i = max + 1; i <= n; i++) {
			A[start] = i;
			find(A, n, start + 1, res);
			A[start] = 0;
		}
	}
}

抱歉!评论已关闭.