[LeetCode - Backtracking] Combinations

fizz 發(fā)布于2019-08-16 10:26 / 2143人閱讀

摘要：本題與類似，都是用回溯法。求中個數(shù)的不同組合，很明顯我們需要注意的就是每個數(shù)字只能出現(xiàn)一次，這點與不同。

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

本題與Combinations Sum類似，都是用回溯法。求1...n中k個數(shù)的不同組合，很明顯我們需要注意的就是每個數(shù)字只能出現(xiàn)一次，這點與Combinations Sum不同。

代碼

 public class Solution {
        List> res=new ArrayList>();
        int num=0;
        public List> combine(int n, int k) {
            num=n;
            if(n==0||k==0) return res;
            combineHelper(1,k,new ArrayList());
            return res;
        }
        private void combineHelper(int index,int count,List pre){
            if(count==0){
                res.add(pre);
                return;
            }
            for(int i=index;i<=num;i++){
                List cur=new ArrayList(pre);
                cur.add(i);
                combineHelper(i+1,count-1,cur);
            }
        }
    }

云服務(wù)器 GPU云服務(wù)器 backtracking Combinations LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/69791.html

相關(guān)文章

leetcode22. Generate Parentheses

摘要：當(dāng)右括號和左括號的剩余量均為時，及為一個最終結(jié)果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護 2019-08-14 18:35 評論0 收藏0
leetcode17 Letter Combinations of a Phone Number

摘要：題目要求也就是說，將數(shù)字對應(yīng)的字母的排列組合的的所有可能結(jié)果都枚舉出來，順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數(shù)據(jù)結(jié)構(gòu)通過來實現(xiàn)。相比于上一種思路中，內(nèi)存占用更小，而且更加靈活。題目要求 Given a digit string, return all possible letter combinations that the numbe...

snowell 2019-08-14 18:09 評論0 收藏0
leetcode39 combination sum

摘要：在這道題中，我結(jié)合了遞歸的思想來。就是將當(dāng)前的值作為一個潛在的結(jié)果值加入一個結(jié)果數(shù)組將數(shù)組作為當(dāng)前結(jié)果傳入下一輪遞歸。題目要求 Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the ca...

luoyibu 2019-08-16 10:33 評論0 收藏0
LeetCode 關(guān)于回溯問題的看法

摘要：回溯算法在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。回溯算法( BackTrack )在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。使用回溯算法解題的一般步驟使用回溯算法解題的一般步驟：針對所給問題得出一般的解空間用回溯搜索方法搜索解空間使用深度優(yōu)先去搜索所有解并包含適當(dāng)?shù)募糁Σ僮? LeetCode 使用回溯算法的題目主要有 36 題，...

ASCH 2019-08-15 13:43 評論0 收藏0
LeetCode[22] Generate Parentheses

摘要：復(fù)雜度思路注意的地方，要限制左括號和右括號。每出現(xiàn)一次左括號，就相對于限定了，最多只能出現(xiàn)那么多右括號。所以，為了完成這種限定，用來控制。不然會有的情況出現(xiàn)。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

Jonathan Shieber 2019-08-14 15:02 評論0 收藏0