在這里之碗，我們再復習一下 LeetCode 第 77 題。剪枝主要的出發(fā)點就在于搔体，我們可以提前做好判斷恨樟，減少不必要的比較開銷。

LeetCode 第 77 題：組合-2

添加打印輸出疚俱，幫助理清程序執(zhí)行流程劝术。

Java 代碼：我們以 ， 為例運行我們的代碼：

public static void main(String[] args) {
    Solution solution = new Solution();
    List<List<Integer>> combine = solution.combine(5, 3);
    System.out.println(combine);
}

可以發(fā)現(xiàn)呆奕，其中綠色的部分养晋，是不能產(chǎn)生結果的分支，但是我們的代碼確實又執(zhí)行到了這部分梁钾。我們可以在 generateCombinations() 函數(shù)中添加如下輸出：

private void generateCombinations(int n, int k, int start, List<Integer> pre) {
    if (pre.size() == k) { // pre.size() == k
        result.add(new ArrayList<>(pre));
        return;
    }
    for (int i = start; i <= n; i++) {
        pre.add(i);
        // 添加的打印語句1
        System.out.println(pre + " new start：" + (i + 1));
        generateCombinations(n, k, i + 1, pre);
        pre.remove(pre.size() - 1);
        // 添加的打印語句2
        System.out.println(pre);

    }
}

此時的打印語句為：

[1] new start：2
[1, 2] new start：3
[1, 2, 3] new start：4
[1, 2]
[1, 2, 4] new start：5
[1, 2]
[1, 2, 5] new start：6
[1, 2]
[1]
[1, 3] new start：4
[1, 3, 4] new start：5
[1, 3]
[1, 3, 5] new start：6
[1, 3]
[1]
[1, 4] new start：5
[1, 4, 5] new start：6
[1, 4]
[1]
[1, 5] new start：6
[1]
[]
[2] new start：3
[2, 3] new start：4
[2, 3, 4] new start：5
[2, 3]
[2, 3, 5] new start：6
[2, 3]
[2]
[2, 4] new start：5
[2, 4, 5] new start：6
[2, 4]
[2]
[2, 5] new start：6
[2]
[]
[3] new start：4
[3, 4] new start：5
[3, 4, 5] new start：6
[3, 4]
[3]
[3, 5] new start：6
[3]
[]
[4] new start：5
[4, 5] new start：6
[4]
[]
[5] new start：6
[]
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

上面的代碼中绳泉，我們發(fā)現(xiàn)：其實如果 pre 已經(jīng)選擇到 [1,4,5] 或者 [2,4,5] 或者 [3,4,5] ，此時后續(xù)的一些代碼就沒有必要執(zhí)行了姆泻，因此繼續(xù)走也不能發(fā)現(xiàn)新的滿足題意的元素零酪。所以干了類似與下面事情，其實有很多步驟是多余的：選擇了 [1,4,5] 以后拇勃， 5 跳出 [1,4,5] 成為 [1,4] , 4 跳出 [1,4] 成為 4 四苇，然后 5 進來，成為 [1,5]潜秋，在進來發(fā)現(xiàn) for 循環(huán)都進不了（因為沒有可選的元素）蛔琅，然后 5 又跳出，接著 1 跳出峻呛。

發(fā)現(xiàn)多余操作：那么我們?nèi)绾伟l(fā)現(xiàn)多余的步驟呢，其實也是有規(guī)律可尋的辜窑，就在 for 循環(huán)中：

for (int i = start; i <= n; i++) {
    pre.add(i);
    generateCombinations(n, k, i + 1, pre);
    pre.remove(pre.size() - 1);
}

這個函數(shù)干的事情钩述，是從 這個區(qū)間里（注意，左右都是閉區(qū)間）穆碎，找到 k-pre.zize() 個元素牙勘。 i <= n 不是每一次都要走完的， i 有一個上限所禀。

尋找規(guī)律：我們再看圖方面，可以發(fā)現(xiàn)一些邊界情況，幫助我們發(fā)下規(guī)律:

當選定了一個元素色徘，即 pre.size() == 1 的時候恭金，接下來要選擇 2 個元素， i 最大的值是 4 褂策，因為從 5 開始選擇横腿，就無解了颓屑；
當選定了兩個元素，即 pre.size() == 2 的時候耿焊，接下來要選擇 1 個元素揪惦， i 最大的值是 5 ，因為從 6 開始選擇罗侯，就無解了器腋。
再如：如果 n = 6 ，k = 4钩杰，
pre.size() == 1 的時候纫塌，接下來要選擇 3 個元素， i 最大的值是 4榜苫，最后一個被選的是 [4,5,6]护戳；
pre.size() == 2 的時候，接下來要選擇 2 個元素垂睬， i 最大的值是 5媳荒，最后一個被選的是 [5,6]；
pre.size() == 3 的時候驹饺，接下來要選擇 1 個元素钳枕， i 最大的值是 6，最后一個被選的是 [6]赏壹；

再如：如果 n = 15 鱼炒，k = 4，
pre.size() == 1 的時候蝌借，接下來要選擇 3 個元素昔瞧， i 最大的值是 13，最后一個被選的是 [13,14,15]菩佑；
pre.size() == 2 的時候自晰，接下來要選擇 2 個元素， i 最大的值是 14稍坯，最后一個被選的是 [14,15]酬荞；
pre.size() == 3 的時候，接下來要選擇 1 個元素瞧哟， i 最大的值是 15混巧，最后一個被選的是 [15]；
多寫幾遍（發(fā)現(xiàn) max(i) 是我們倒著寫出來）勤揩，我么就可以發(fā)現(xiàn) max(i) 與 接下來要選擇的元素貌似有一點關系咧党，很容易知道：
max(i) + 接下來要選擇的元素個數(shù) - 1 = n，其中雄可， 接下來要選擇的元素個數(shù) = k - pre.size()凿傅，整理得到：

缠犀。

所以，我們的剪枝過程就可以體現(xiàn)在聪舒，把 i <= n 改成 i <= n - (k - pre.size()) + 1 ：

for (int i = start; i <= n - (k - pre.size()) + 1; i++) { 
    pre.add(i); 
    generateCombinations(n, k, i + 1, pre); 
    pre.remove(pre.size() - 1); 
} 

// p 可以聲明成一個棧
// i 的極限值滿足： n - i + 1 = (k-pre.size())辨液。
// n - i + 1 是閉區(qū)間 [i,n] 的長度。
// k - pre.size() 是剩下還要尋找的數(shù)的個數(shù)箱残。
private void findCombinations(int n, int k, int index, Stack<Integer> p) {
    if (p.size() == k) {
        result.add(new ArrayList<>(p));
        return;
    }
    for (int i = index; i <= n - (k - p.size()) + 1; i++) {
        p.push(i);
        findCombinations(n, k, i + 1, p);
        p.pop();
    }
}

觀察結果：此時打印輸出語句就會少很多滔迈。

[1] new start：2
[1, 2] new start：3
[1, 2, 3] new start：4
[1, 2]
[1, 2, 4] new start：5
[1, 2]
[1, 2, 5] new start：6
[1, 2]
[1]
[1, 3] new start：4
[1, 3, 4] new start：5
[1, 3]
[1, 3, 5] new start：6
[1, 3]
[1]
[1, 4] new start：5
[1, 4, 5] new start：6
[1, 4]
[1]
[]
[2] new start：3
[2, 3] new start：4
[2, 3, 4] new start：5
[2, 3]
[2, 3, 5] new start：6
[2, 3]
[2]
[2, 4] new start：5
[2, 4, 5] new start：6
[2, 4]
[2]
[]
[3] new start：4
[3, 4] new start：5
[3, 4, 5] new start：6
[3, 4]
[3]
[]
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

練習1：LeetCode 第 39 題：組合總和

傳送門：英文網(wǎng)址：39. Combination Sum ，中文網(wǎng)址：39. 組合總和 被辑。

給定一個無重復元素的數(shù)組 candidates 和一個目標數(shù) target 燎悍，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的數(shù)字可以無限制重復被選取盼理。

說明：

• 所有數(shù)字（包括 target）都是正整數(shù)谈山。
• 解集不能包含重復的組合。

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

求解關鍵：注意分析題意宏怔，找到可以減少判斷的條件：

1奏路、這道題猛地一看好像跟前面的問題搭不上關系，因為題目中說“candidates 中的數(shù)字可以無限制重復被選取”臊诊；
2鸽粉、但其實仔細想想就會發(fā)現(xiàn)，我們每次取數(shù)字的時候抓艳，還從原點開始取就行了呀触机，是不是很酷；
3玷或、為了達到提前判斷循環(huán)結束的效果儡首，我們可以先對數(shù)組排個序，如果起點數(shù)字比剩下的和還要大偏友，后面的循環(huán)就沒有必要進行下去了椒舵。此時，我們在 for 循環(huán)里加判斷约谈，盡量減少了系統(tǒng)棧的調(diào)用深度。

Java 實現(xiàn)：沒有做剪枝優(yōu)化的版本犁钟。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// https://leetcode-cn.com/problems/combination-sum/description/
public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    // residue 定義為剩余棱诱，這個剩余一開始等于 target，在遞歸中涝动，它的值會越來越小
    // 因為題目中說了"所有數(shù)字（包括 target）都是正整數(shù)"迈勋。
    private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
        // 因為可以無限選取，所以 residue 只能小于 0 或者等于 0
        if (residue < 0) {
            return;
        }
        // 一定是剩下的那個數(shù)為 0 了醋粟，才表示我們所選的數(shù)字的和剛好等于 target
        if (residue == 0) {
            res.add(new ArrayList<>(pre));
            return;
        }
        for (int i = start; i < len; i++) {
            // 每個數(shù)有選擇和不選擇靡菇，因此嘗試了一種解的可能以后要進行狀態(tài)重置
            pre.add(candidates[i]);
            // 【關鍵】因為元素可以重復使用重归，這里遞歸傳遞下去的是 i 而不是 i + 1
            findCombinationSum(residue - candidates[i], i, pre);
            pre.pop();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        this.len = len;
        this.candidates = candidates;
        findCombinationSum(target, 0, new Stack<>());
        return res;
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        Solution solution = new Solution();
        List<List<Integer>> combinationSum = solution.combinationSum(candidates, target);
        System.out.println(combinationSum);
    }
}

Java 代碼：剪枝的版本。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution2 {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
        if (residue == 0) {
            res.add(new ArrayList<>(pre));
            return;
        }
        // 優(yōu)化添加的代碼2：在循環(huán)的時候做判斷厦凤，盡量避免系統(tǒng)棧的深度
        // residue - candidates[i] 表示下一輪的剩余鼻吮，如果下一輪的剩余都小于 0 ，就沒有必要進行后面的循環(huán)了
        // 這一點基于原始數(shù)組是排序數(shù)組的前提较鼓，因為如果計算后面的剩余椎木，只會越來越小
        for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
            pre.add(candidates[i]);
            // 【關鍵】因為元素可以重復使用，這里遞歸傳遞下去的是 i 而不是 i + 1
            findCombinationSum(residue - candidates[i], i, pre);
            pre.pop();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        // 優(yōu)化添加的代碼1：先對數(shù)組排序博烂，可以提前終止判斷
        Arrays.sort(candidates);
        this.len = len;
        this.candidates = candidates;
        findCombinationSum(target, 0, new Stack<>());
        return res;
    }
}

練習2：LeetCode 第 40 題：組合總和 II

傳送門：英文網(wǎng)址：40. Combination Sum II 香椎，中文網(wǎng)址：40. 組合總和 II 。

給定一個數(shù)組 candidates 和一個目標數(shù) target 禽篱，找出 candidates 中所有可以使數(shù)字和為 target 的組合畜伐。

candidates 中的每個數(shù)字在每個組合中只能使用一次。

說明：

• 所有數(shù)字（包括目標數(shù)）都是正整數(shù)躺率。
• 解集不能包含重復的組合玛界。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
所求解集為:
[
  [1,2,2],
  [5]
]

求解關鍵：找到如何在結果集中去除重復的方法。

1肥照、與第 39 題的區(qū)別脚仔，第 39 題的數(shù)組沒有重復數(shù)字，可以使用多次舆绎；第 40 題的數(shù)組有重復數(shù)字鲤脏，只能使用一次，具體就體現(xiàn)在進行下一層遞歸的時候吕朵，起始的那個索引值是多少猎醇；
（2）很容易想到，應該先對給出的數(shù)組進行排序努溃，排序的目的有兩個：其一是硫嘶，可以提前終止循環(huán)，其二是“在遞歸函數(shù)的調(diào)用中梧税，同一深度的一個值只能使用一次”沦疾，這一處理也幾乎成為了標準寫法，或許剛剛開始接觸的時候并不好理解第队，應該使用具體的例子畫出圖來理解哮塞，然后多做一些類似練習，理解代碼為什么那樣寫凳谦。

C++ 寫法：

LeetCode 第 40 題：組合總和 II-1

Java 寫法：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

// https://leetcode-cn.com/problems/combination-sum-ii/description/
public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    // residue 表示剩余忆畅，這個值一開始等于 target，基于題目中說明的"所有數(shù)字（包括目標數(shù)）都是正整數(shù)"這個條件
    // residue 在遞歸遍歷中尸执，只會越來越小
    private void findCombinationSum2(int residue, int begin, Stack<Integer> stack) {
        if (residue == 0) {
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = begin; i < len && residue - candidates[i] >= 0; i++) {
            // 這一步之所以能夠生效家凯，其前提是數(shù)組一定是排好序的缓醋，這樣才能保證：
            // 在遞歸調(diào)用的統(tǒng)一深度（層）中，一個元素只使用一次绊诲。
            // 這一步剪枝操作基于 candidates 數(shù)組是排序數(shù)組的前提下
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            stack.add(candidates[i]);
            // 【關鍵】因為元素不可以重復使用送粱，這里遞歸傳遞下去的是 i + 1 而不是 i
            findCombinationSum2(residue - candidates[i], i + 1, stack);
            stack.pop();
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        this.len = len;
        // 先將數(shù)組排序，這一步很關鍵
        Arrays.sort(candidates);
        this.candidates = candidates;
        findCombinationSum2(target, 0, new Stack<>());
        return res;
    }

    public static void main(String[] args) {
        int[] candidates = {2, 5, 2, 1, 2};
        int target = 5;
        Solution solution = new Solution();
        List<List<Integer>> combinationSum2 = solution.combinationSum2(candidates, target);
        System.out.println(combinationSum2);
    }
}

練習3：LeetCode 第 216 題：組合總和 III

傳送門：組合總和 III驯镊。

找出所有相加之和為 n 的 k 個數(shù)的組合葫督。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復的數(shù)字板惑。

說明：

• 所有數(shù)字都是正整數(shù)橄镜。
• 解集不能包含重復的組合。

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]

示例 2:

輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]

要求：找出所有相加之和為 n 的 k 個數(shù)的組合冯乘。組合中只允許含有1 - 9的正整數(shù)洽胶，并且每種組合中不存在重復的數(shù)字。

Java 代碼：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// https://leetcode-cn.com/problems/combination-sum-iii/description/
// 找出所有相加之和為 n 的 k 個數(shù)的組合裆馒。組合中只允許含有1 - 9的正整數(shù)姊氓，并且每種組合中不存在重復的數(shù)字。

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private int k;

    private void findCombinationSum3(int target, int depth, int start, Stack<Integer> stack) {
        if (target == 0 && depth == k) {
            res.add(new ArrayList<>(stack));
            return;
        }
        // 注意：題目中要求組合中只允許含有 1 - 9 的正整數(shù)喷好。
        for (int i = start; i <= 9 && target - i >= 0; i++) {
            stack.add(i);
            findCombinationSum3(target - i, depth + 1, i + 1, stack);
            stack.pop();
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k < 0 || n < 0 || k > n) {
            return res;
        }

        if (n > (9 * k - (k * (k - 1)) / 2)) {
            return res;
        }

        this.k = k;
        // 注意翔横，深度應該從 0 開始，往下走一層梗搅，深度加 1 禾唁，加到 3 為止
        findCombinationSum3(n, 0, 1, new Stack<>());
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int k = 3;
        int n = 15;
        List<List<Integer>> combinationSum3 = solution.combinationSum3(k, n);
        System.out.println(combinationSum3);
    }
}

練習4：LeetCode 第 78 題：子集

傳送門：78. 子集。

給定一組不含重復元素的整數(shù)數(shù)組 nums无切，返回該數(shù)組所有可能的子集（冪集）荡短。

說明：解集不能包含重復的子集。

示例:

輸入: nums = [1,2,3]
輸出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路：對每一位的元素哆键，有選擇和不選擇兩種做法掘托。

Python 代碼：

# 78. 子集
# 給定一組不含重復元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）籍嘹。
# 說明：解集不能包含重復的子集闪盔。

# 關鍵詞：不含重復元素
# 參考資料：花花醬 https://mp.weixin.qq.com/s/AWuv4p-RQyoCW22DczfTVA
# 參考資料：花花醬 https://mp.weixin.qq.com/s/AWuv4p-RQyoCW22DczfTVA

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []

        def dfs(max_count, begin, path):
            # n 表示當前全排列的個數(shù)
            # cur 表示已經(jīng)拿到的 path

            if max_count == len(path):
                # 夠數(shù)了，就加到結果集中
                res.append(path.copy())
                return
            for i in range(begin, len(nums)):

                # 加進去表示考慮這個元素
                path.append(nums[i])
                # 注意：這里是 i
                dfs(max_count, i + 1, path)

                # pop() 表示不考慮這個元素
                path.pop()

        for i in range(len(nums) + 1):
            dfs(i, 0, [])
        return res


if __name__ == '__main__':
    nums = [1, 2, 3]
    solution = Solution()
    result = solution.subsets(nums)
    print(result)

Java 寫法：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/subsets/description/
 */
public class Solution2 {

    private void findSubsets(int[] nums, int begin, int len, Stack<Integer> stack, List<List<Integer>> res) {
        // 在遍歷的過程中辱士，收集
        res.add(new ArrayList<>(stack));
        for (int i = begin; i < len; i++) {
            stack.add(nums[i]);
            findSubsets(nums, i + 1, len, stack, res);
            stack.pop();
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        findSubsets(nums, 0, len, new Stack<>(), res);
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution2 solution = new Solution2();
        List<List<Integer>> subsets = solution.subsets(nums);
        System.out.println(subsets);
    }
}

練習5：LeetCode 第 90 題：子集 II

傳送門：英文網(wǎng)址：90. Subsets II 锭沟，中文網(wǎng)址：90. 子集 II 。

給定一個可能包含重復元素的整數(shù)數(shù)組 nums识补，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復的子集辫红。

示例:

輸入: [1,2,2]
輸出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Python 代碼：

# 90. 子集 II
# 給定一個可能包含重復元素的整數(shù)數(shù)組 nums凭涂，返回該數(shù)組所有可能的子集（冪集）祝辣。
# 說明：解集不能包含重復的子集。

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        l = len(nums)
        if l == 0:
            return []
        nums.sort()
        res = []

        def dfs(max_count, begin, path):
            if max_count == len(path):
                res.append(path.copy())
                return
            for i in range(begin, len(nums)):
                # 注意：這里不要寫成 i > 0
                if i > begin and nums[i - 1] == nums[i]:
                    continue
                path.append(nums[i])
                dfs(max_count, i + 1, path)
                path.pop()

        for max_count in range(0, l + 1):
            dfs(max_count, 0, [])
        return res


if __name__ == '__main__':
    nums = [1, 2, 2]
    solution = Solution()
    result = solution.subsetsWithDup(nums)
    print(result)

Java 代碼：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/subsets-ii/description/
 */
public class Solution {

    private void findSubsetsWithDup(int[] nums, int maxCount, int begin, int len,
                                    boolean[] marked, Stack<Integer> stack,
                                    List<List<Integer>> res) {
        if (maxCount == stack.size()) {
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = begin; i < len; i++) {
            if (!marked[i]) {
                // 去重都有這一步加上排序
                if (i > begin && nums[i] == nums[i - 1]) {
                    continue;
                }
                marked[i] = true;
                stack.add(nums[i]);
                findSubsetsWithDup(nums, maxCount, i + 1, len, marked, stack, res);
                stack.pop();
                marked[i] = false;
            }
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        // 排序很關鍵
        Arrays.sort(nums);
        boolean[] marked = new boolean[len];
        for (int i = 0; i <= len; i++) {
            findSubsetsWithDup(nums, i, 0, len, marked, new Stack<>(), res);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 2};
        List<List<Integer>> subsetsWithDup = solution.subsetsWithDup(nums);
        System.out.println(subsetsWithDup);
    }
}

練習6：LeetCode 第 401 題：二進制手表問題

傳送門：401. 二進制手表切油。

二進制手表頂部有 4 個 LED 代表小時（0-11）蝙斜，底部的 6 個 LED 代表分鐘（0-59）。

每個 LED 代表一個 0 或 1澎胡，最低位在右側孕荠。

LeetCode 第 401 題：二進制手表問題

例如，上面的二進制手表讀取 “3:25”攻谁。

給定一個非負整數(shù) n 代表當前 LED 亮著的數(shù)量稚伍，返回所有可能的時間。

案例:

輸入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

注意事項:

• 輸出的順序沒有要求戚宦。
• 小時不會以零開頭个曙，比如 “01:00” 是不允許的，應為 “1:00”受楼。
• 分鐘必須由兩位數(shù)組成垦搬，可能會以零開頭，比如 “10:2” 是無效的艳汽，應為 “10:02”猴贰。

典型的組合問題。

Java 代碼：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// https://leetcode-cn.com/problems/binary-watch/description/

public class Solution {

    private List<String> res = new ArrayList<>();

    private int[] hourArr = {8, 4, 2, 1};
    private int[] minuteArr = {32, 16, 8, 4, 2, 1};

    public List<String> readBinaryWatch(int num) {
        if (num > 10 || num < 0) {
            return res;
        }
        for (int i = 0; i <= num; i++) {
            // 應該定義組合
            List<Integer> hourCombination = findCombination(hourArr, i);
            List<Integer> minuteCombination = findCombination(minuteArr, num - i);
            for (int j = 0; j < hourCombination.size(); j++) {
                if (hourCombination.get(j) > 11) {
                    continue;
                }
                for (int k = 0; k < minuteCombination.size(); k++) {
                    if (minuteCombination.get(k) > 59) {
                        continue;
                    }
                    res.add(hourCombination.get(j) + ":" + (minuteCombination.get(k) < 10 ? "0" + minuteCombination.get(k) : minuteCombination.get(k)));
                }
            }
        }
        return res;
    }


    private List<Integer> findCombination(int[] arr, int count) {
        List<Integer> res = new ArrayList<>();
        findCombination(arr, count, 0, new Stack<>(), res);
        return res;
    }


    private Integer sum(List<Integer> pre) {
        int sum = 0;
        for (int i = 0; i < pre.size(); i++) {
            sum += pre.get(i);
        }
        return sum;
    }

    private void findCombination(int[] arr, int count, int start, Stack<Integer> pre, List<Integer> res) {
        if (pre.size() == count) {
            res.add(sum(pre));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            pre.push(arr[i]);
            findCombination(arr, count, i + 1, pre, res);
            pre.pop();
        }
    }


    public static void main(String[] args) {
        // write your code here
        Solution solution = new Solution();
        List<String> readBinaryWatch = solution.readBinaryWatch(2);
        System.out.println(readBinaryWatch);


    }
}

（本節(jié)完）