leetcode: Combination Sum

问题描述：

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.

Note:

• 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.

 

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

 

原问题链接：https://leetcode.com/problems/combination-sum/

 

问题分析

方法一

　　这个问题是给定一个数组，里面的元素可以重复选择。对于一个给定的目标数字，需要求数组里所有若干个数相加等于该目标数字的组合。由于题目的要求组合的元素必须是不能递减的顺序。所以需要一开始对这个数组排序。剩下的就是要来找若干个数使得它们的和等于目标数字。

　　该怎么去找呢？对于给定的数组candidates和我们的目标值target。假设我们取了candidates里面位置i的元素的值来凑这个target。如果target > candidates[i]，这就说明我们这个数字是可以加进来，不过接下来要考虑剩下的部分组成target - candidates[i]的问题。对于其他情况来说如果target < candidates[i]，很明显，这种情况不符合我们的要求，我们就要返回。而如果target == candidates[i]呢，则表示我们正好构成了一个结果，需要将所有拼凑的数字返回。

　　既然这里提到我们要拼凑这些数字来让它们等于target，并且要求将这些数字最终返回。所以在实现的时候应该考虑用一个List来保存每次符合条件的数字。另外，在前面发现要进一步递归的时候，该怎么来做下一步的递归呢？结合前面题目的要求，后面的取值不能小于前面的值，所以递归的时候下一步只能从i及i后面的元素来取。

　　按照这种思路实现的代码如下：

 

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Arrays.sort(candidates);
        recurse(new ArrayList<Integer>(), target, candidates, 0, ret);
        return ret;
    }
    
    private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) {
        if (target == 0) {
            ret.add(list);
            return;
        }
        for(int i = index; i < candidates.length; i++) {
            int newTarget = target - candidates[i];
            if(newTarget >= 0) {
                List<Integer> copy = new ArrayList<Integer>(list);
                copy.add(candidates[i]);
                recurse(copy, newTarget, candidates, i, ret);
            } else
                break;
        }
    }
}

 

 

方法二

    其实，前面的问题描述里头已经有一个很明显的痕迹。就是要求里面若干个数的和使得它们等于target。对于这个问题来说有一个递归的思路，就是假设target大于candidates里面的若干个数。那么这个问题就可以进一步转化成target减去这些值的递归子问题。因为这里一个问题可以递归成多个子问题。而且很多问题有可能是重叠的。这就很容易让人想到动态规划的思路。

　　针对这个问题，动态规划的大致套路就是首先定义一个target长度的数组或者集合，用来保存它们递归过程中间的值。然后再从数值１到target来逐步遍历构建这个数组。这种思路的伪码实现如下：

 

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>[] dp = (List<List<Integer>>[]) new Object[target + 1];
        for(int i = 1; i <= target; i++) {
            for(int j = 0; j < candidates.length && candidates[j] <= i; j++) {
                dp[i] = merge(dp[i - candidates[j]], dp[candidates[j]]);
            }
        }
        return dp[target];
    }

 　　上述的伪码只是做了一个大致的描述。在实际的实现中因为java中不能直接声明泛型的数组，还是需要做一些变动。另外，对于两个部分结果的合并也有很多细节需要考虑。我们需要将candiates[j]的值加到原来列表里的每个元素里去。当然，还是要考虑过滤掉candidates[j]大于里面元素第一个成员的情况。

　　按照这个思路，另外一种实现的代码如下：

 

public class Solution {
    public List<List<Integer>> combinationSum(int[] cands, int t) {
        Arrays.sort(cands); // sort candidates to try them in asc order
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
            List<List<Integer>> newList = new ArrayList(); // combs for curr i
            // run through all candidates <= i
            for (int j = 0; j < cands.length && cands[j] <= i; j++) {
                // special case when curr target is equal to curr candidate
                if (i == cands[j]) newList.add(Arrays.asList(cands[j]));
                // if current candidate is less than the target use prev results
                else for (List<Integer> l : dp.get(i-cands[j]-1)) {
                    if (cands[j] <= l.get(0)) {
                        List cl = new ArrayList<>();
                        cl.add(cands[j]); cl.addAll(l);
                        newList.add(cl);
                    }
                }
            }
            dp.add(newList);
        }
        return dp.get(t-1);
    }
}

 

 

总结

     求若干个数字的和等于目标数字，其实其解法有好几种。比如递归法，或者深度优先遍历法或者动态规划法。重点是不同方法的思路和一些结果合并的细节。