254. Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

**Note: **

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

**Examples: **

input: 1
output: 
[]

input: 37
output: 
[]

input: 12
output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

一刷
題解: DFS + backtracking, 265 ms

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(res, list, n, 2);
        return res;
    }
    
    public void dfs(List<List<Integer>> res, List<Integer> list, int n, int start){
        if(n<=1){
            if(list.size()>1) res.add(new ArrayList<>(list));
            return;
        }
        
//由于end可能包含自己称勋,如4=2*2,第二次recursion傳入2,于是有等號(hào),list加入res時(shí)要判斷size是否大于1
        for(int i=start; i<=n; i++){
            if(n%i == 0){
                list.add(i);
                dfs(res, list, n/i, i);
                list.remove(list.size()-1);
            }
        }
    }
}

方法2衣吠, factor都是成雙成對(duì)出現(xiàn)的倍谜,例如如果n%i == 0, 那么 {i, n/i}一定是滿足條件的一個(gè)解。2ms

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        if(n <= 3)  return ret;
        List<Integer> path = new LinkedList<Integer>();
        getFactors(2, n, path, ret);
        return ret;
    }
    
    private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){
       for(int i = start; i <= Math.sqrt(n); i++){
           if(n % i == 0 && n/i >= i){  // The previous factor is no bigger than the next
               path.add(i);
               path.add(n/i);
               ret.add(new LinkedList<Integer>(path));
               path.remove(path.size() - 1);
//下次的start = I, 保證不會(huì)再拆出比左邊更小的弄息,避免重復(fù)
               getFactors(i, n/i, path, ret);
               path.remove(path.size() - 1);
           }
       }
    }
}

二刷
同上

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        helper(2, n, path, res);
        return res;
    }
    
    private void helper(int start, int n, List<Integer> path, List<List<Integer>> res){
        int sqrt = (int) Math.sqrt(n);
        for(int i=start; i<=sqrt; i++){
            if(n%i == 0){
                path.add(i);
                path.add(n/i);
                res.add(new ArrayList<Integer>(path));
                path.remove(path.size()-1);
                helper(i, n/i, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市勤婚,隨后出現(xiàn)的幾起案子摹量,更是在濱河造成了極大的恐慌,老刑警劉巖蛔六,帶你破解...
    沈念sama閱讀 222,627評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件荆永,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡国章,警方通過(guò)查閱死者的電腦和手機(jī)具钥,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)液兽,“玉大人骂删,你說(shuō)我怎么就攤上這事掌动。” “怎么了宁玫?”我有些...
    開(kāi)封第一講書人閱讀 169,346評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵粗恢,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我欧瘪,道長(zhǎng)眷射,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書人閱讀 60,097評(píng)論 1 300
  • 正文 為了忘掉前任佛掖,我火速辦了婚禮妖碉,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘芥被。我一直安慰自己欧宜,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,100評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布拴魄。 她就那樣靜靜地躺著冗茸,像睡著了一般。 火紅的嫁衣襯著肌膚如雪匹中。 梳的紋絲不亂的頭發(fā)上夏漱,一...
    開(kāi)封第一講書人閱讀 52,696評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音顶捷,去河邊找鬼麻蹋。 笑死,一個(gè)胖子當(dāng)著我的面吹牛焊切,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播芳室,決...
    沈念sama閱讀 41,165評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼专肪,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了堪侯?” 一聲冷哼從身側(cè)響起嚎尤,我...
    開(kāi)封第一講書人閱讀 40,108評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎伍宦,沒(méi)想到半個(gè)月后芽死,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,646評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡次洼,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,709評(píng)論 3 342
  • 正文 我和宋清朗相戀三年关贵,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片卖毁。...
    茶點(diǎn)故事閱讀 40,861評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡揖曾,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情炭剪,我是刑警寧澤练链,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站奴拦,受9級(jí)特大地震影響媒鼓,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜错妖,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,196評(píng)論 3 336
  • 文/蒙蒙 一绿鸣、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧站玄,春花似錦枚驻、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,698評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至晾剖,卻和暖如春锉矢,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背齿尽。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,804評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工沽损, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人循头。 一個(gè)月前我還...
    沈念sama閱讀 49,287評(píng)論 3 379
  • 正文 我出身青樓绵估,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親卡骂。 傳聞我的和親對(duì)象是個(gè)殘疾皇子国裳,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,860評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,585評(píng)論 0 23
  • 對(duì)每一位渴望找到更有效教養(yǎng)孩子方法的家長(zhǎng),我由衷推薦來(lái)到“正面管教課堂”全跨;對(duì)每一位渴望自我成長(zhǎng)缝左、渴望改善周遭“關(guān)系...
    丑蘋果閱讀 145評(píng)論 0 0
  • 小時(shí)候最開(kāi)心的事情莫過(guò)于狂奔于草地里渺杉,追著蝴蝶跑來(lái)跑去。白的挪钓,黃的是越,灰的,紅的碌上,各色的蝴蝶在那個(gè)夏末秋初的季節(jié)里英妓,...
    青青666666閱讀 370評(píng)論 2 1
  • 白襯衫挽放,粉色裙 記憶躲在那年夏天的拐角 看風(fēng)吹動(dòng)墻外的柳梢 我能聽(tīng)見(jiàn)心中的小鹿在奔跑 傻傻的忘了微笑 我把醞釀了許...
    衡水文化王新良閱讀 180評(píng)論 0 1
  • 靈感:家族信托好頂贊 (慢速,中低音蔓纠,長(zhǎng)吁悵惘) 空格表停頓 辑畦,和換行表斷句 世間人,總是帶著破綻 時(shí)間流轉(zhuǎn)腿倚,漆夜...
    大美不仁閱讀 632評(píng)論 0 2