​LeetCode刷題實戰39:組合總和

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做 組合總和，我們先來看題面：

https://leetcode-cn.com/problems/combination-sum

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

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

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

題意給定一個無重複元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。candidates 中的數字可以無限制重複被選取。樣例

示例 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]
]

題解回溯法回溯算法關鍵在於:不合適就退回上一步，然後通過約束條件, 減少時間複雜度.假設candidates = [2, 3, 6, 7]，target = 7
以 target = 7 為根結點，每一個分支做減法。減到 0 或者負數的時候，剪枝。其中，減到 0 的時候結算，這裡 「結算」 的意思是添加到結果集。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, res, 0, new ArrayList<Integer>());
        return res;
    }
    private void backtrack(int[] candidates, int target, List<List<Integer>> res,
        int i, ArrayList<Integer> tmp_list) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(tmp_list)); return;
        }
        for (int start = i; start < candidates.length; start++) {
            if (target < candidates[start]) break;
            tmp_list.add(candidates[start]);
            backtrack(candidates, target - candidates[start], res, start, tmp_list);
            tmp_list.remove(tmp_list.size() - 1);
        }
    }
}

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。