Combination Sum

大家新年快樂。

今天是一道有關(guān)數(shù)組和迭代的題目，來自LeetCode，難度為Medium，Acceptance為29.5%。

題目如下

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] 

解題思路及代碼見閱讀原文

回復0000查看更多題目

解題思路

首次，該題還是有一定難度的，但是通過率并不低，思路也較為清晰。

然后，我們來分析該題。因為根據(jù)題意，每個數(shù)字可以選0次或者任意多次，所以這里很容易想到用遞歸；其次，因為這里要求所有的可能，為了避免重復，我們先對所有數(shù)排序。

然后遞歸，就要想遞歸的終止條件：

• 第一，當前值已經(jīng)等于T了，此時可以終止，因為題目中給出了所有數(shù)都是正數(shù)。

• 第二，因為所有數(shù)都是正數(shù)，所以當前遍歷到的數(shù)比T-current大的時候，可以終止。

最后，因為每個數(shù)可以選擇多次，所以遞歸過程中不能每次遍歷下一個數(shù)字，還是要從該數(shù)字開始，直到滿足以上2個終止條件。

我們來看代碼。

代碼如下

Java版

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(ret, new LinkedList<Integer>(), 0, target, candidates);
        return ret;
    }
    
    public void dfs(List<List<Integer>> ret, LinkedList<Integer> list, int start, int gap,  int[] candidates) {
        if(gap == 0) {
            ret.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = start; i < candidates.length && gap >= candidates[i]; i++) {
            list.add(candidates[i]);
            dfs(ret, list, i, gap - candidates[i], candidates);
            list.removeLast();
        }
    }
}

關(guān)注我
該公眾號會每天推送常見面試題，包括解題思路是代碼，希望對找工作的同學有所幫助

image