[LeetCode - Backtracking] Combinations

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

摘要：本題與類似，都是用回溯法。求中個(gè)數(shù)的不同組合，很明顯我們需要注意的就是每個(gè)數(shù)字只能出現(xiàn)一次，這點(diǎ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個(gè)數(shù)的不同組合，很明顯我們需要注意的就是每個(gè)數(shù)字只能出現(xiàn)一次，這點(diǎ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);
            }
        }
    }

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69791.html

相關(guān)文章

leetcode22. Generate Parentheses

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

騫諱護(hù) 2019-08-14 18:35 評(píng)論0 收藏0
leetcode17 Letter Combinations of a Phone Number

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

snowell 2019-08-14 18:09 評(píng)論0 收藏0
leetcode39 combination sum

摘要：在這道題中，我結(jié)合了遞歸的思想來(lái)。就是將當(dāng)前的值作為一個(gè)潛在的結(jié)果值加入一個(gè)結(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 評(píng)論0 收藏0
LeetCode 關(guān)于回溯問(wèn)題的看法

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

ASCH 2019-08-15 13:43 評(píng)論0 收藏0
LeetCode[22] Generate Parentheses

摘要：復(fù)雜度思路注意的地方，要限制左括號(hào)和右括號(hào)。每出現(xiàn)一次左括號(hào)，就相對(duì)于限定了，最多只能出現(xiàn)那么多右括號(hào)。所以，為了完成這種限定，用來(lái)控制。不然會(huì)有的情況出現(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 評(píng)論0 收藏0