LeetCode如何解決組合問題

這篇文章主要介紹LeetCode如何解決組合問題，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

題目

給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合。

示例:

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

代碼

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }

    public void dfs(int cur, int n, int k) {
        // 剪枝：temp 長(zhǎng)度加上區(qū)間 [cur, n] 的長(zhǎng)度小于 k，不可能構(gòu)造出長(zhǎng)度為 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 記錄合法的答案
        if (temp.size() == k) {
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        // 考慮選擇當(dāng)前位置
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        // 考慮不選擇當(dāng)前位置
        dfs(cur + 1, n, k);
    }

}

以上是“LeetCode如何解決組合問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！