Paste_Image.png

My code:

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

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 0 || k <= 0 || k > n)
            return result;
        ArrayList<Integer> sample = new ArrayList<Integer>();

        combine(1, n, k, sample, result);
        
        return result;
    }
    
    private void combine(int begin, int end, int k, ArrayList<Integer> sample, ArrayList<List<Integer>> result) {
        if (k <= 0)
            result.add(new ArrayList<Integer>(sample));
        else {
            for (int i = begin; i <= end; i++) {
                sample.add(i);
                combine(i + 1, end, k - 1, sample, result);
                sample.remove(sample.size() - 1);
            }
            
            
        }   
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        System.out.println(test.combine(5,3));
        
        
    }
}

My test result:

Paste_Image.png

好久沒有做題了被环。。详幽。十天筛欢。等等說。

這道題目著實不錯啊。思路到現(xiàn)在也是精神上理解了下悴能。
其實就是揣钦。比如 5, 3

那么一開始，
1漠酿， 2冯凹， 3 進袋。
然后 有個刪除成員的細節(jié)操作炒嘲，所以又變?yōu)椋?br> 1, 2 繼續(xù)for 循環(huán)
然后 i = 4. 于是宇姚。
1, 2, 4 進袋。
1, 2, 5. 進袋夫凸。
然后for循環(huán)結束浑劳。整個函數(shù)結束，跳轉到上一個遞歸處夭拌。即魔熏。
1， 然后插入2.
于是鸽扁，刪除2蒜绽，繼續(xù)for循環(huán)。
插入3桶现， 于是
1躲雅， 3， 繼續(xù)遞歸骡和。相赁。
以此類推。
我之前的確一直有這樣的迷惑慰于。
ArrayList, Queue, Stack 這些可以存儲數(shù)據(jù)的包類钮科，該如何在遞歸思想中保證其唯一性。
比如婆赠。
ArrayList a;
recursion(5, a);
...

當此處繼續(xù)對a進行操作時跺嗽，a的內(nèi)容已經(jīng)發(fā)生了變化∫吃澹可能多了一些元素桨嫁，也可能少了一些元素。因為他是和遞歸中的那些ArrayList 引用指向的同一個內(nèi)存塊份帐。所以是統(tǒng)一的璃吧。
所以這段代碼有個細節(jié)。

if (k <= 0)
            result.add(new ArrayList<Integer>(sample));

為什么要新new一個ArrayList對象呢废境？因為儲存在result這個范圍內(nèi)的仍然是指針畜挨，指向sample的那個內(nèi)存塊筒繁。如果不新new一個然后把原內(nèi)容拷貝進來，那么就是仍指向原內(nèi)存巴元。那么存儲的所有的指針都是指向同一個內(nèi)存塊sample毡咏，然后打印出來的內(nèi)容都是sample最后狀態(tài)的內(nèi)容。所以必須先new一個逮刨。

這個算法還是一如既往的細致呕缭，靈巧。贊修己！

好久沒刷題了恢总。一恍惚，十天過去了睬愤，本來這十天可以干很多事的片仿。算了，暑假在家沒有怎么休息過尤辱，之前的確過于認真了砂豌，就算放松這十天吧。
哎光督，馬上就要走了阳距，沒想到，在英國期盼的這些事可帽，
見到爸媽然后狂吃美食，畢業(yè)典禮和同學的狂歡窗怒，和丹妮碰面一起旅行映跟，和童年的小伙伴一起聚聚。扬虚。努隙。這些事，這些盼了半年的事辜昵，這些一想起來就激動不已的事荸镊，竟然就這么過去了。
其實很多都做得還不夠好堪置，玩的不夠盡興躬存。尤其是畢業(yè)典禮。剛回校三天舀锨，剛適應同學的體溫岭洲，學校就強制離校了。
和丹妮坎匿，時間實在是太短了盾剩，短的我想帶她去各處玩卻發(fā)現(xiàn)哪個地方時間都是那么的緊雷激。你至少給我十天啊，老天告私。??
這個世界上有條路屎暇，叫做， California State Route 1. I hope I can drive you through this long road, my girl, away from anything, everything, just you, and me.
爸媽的話驻粟，我內(nèi)心是無比愛他們的根悼，但是總覺得說出來肉麻，然后說不出來格嗅。有時候還故意氣氣他們番挺，但他們的確為了做了太多太多。
昨天老爸50歲生日屯掖，但是過得很簡單玄柏，就我和我媽陪著他，我們?nèi)齻€人贴铜。
他對我提出了他的要求粪摘，
第一，留學在外绍坝，人身安全第一位徘意，絕對要注意安全，維護身體健康轩褐。
第二椎咧，要做一個讓爸媽說起來覺得驕傲的兒子。
我會把介，努力去做到的勤讽，為了你們，也為了我拗踢。
今天去和表哥還有他女朋友吃了一頓飯脚牍，挺好的，我對她也挺滿意的巢墅。心里不知道為什么诸狭，挺高興的，好久沒這么高興了君纫。也許他是我內(nèi)心中驯遇，認為的，很重要很重要的人吧蓄髓。
但是表哥工作最近被辭了妹懒，然后還沒找到工作，這個事也一直瞞著那個姑娘双吆，畢竟表哥條件不是很好眨唬，人家姑娘已經(jīng)很好了会前，如果知道他現(xiàn)在沒了工作，對于匾竿，結婚瓦宜，還是會猶豫一些吧。所以瞞著她岭妖，打算先找到工作再說临庇。
從小到大，我總覺得昵慌，因為一些自己弱的原因而去隱瞞假夺，而去騙人，給自己所帶來的屈辱斋攀，遠比把這種弱的原因暴露出來更加讓人感到羞恥已卷。我一直記得小時候考得不好，別人問我成績淳蔼，我媽想撒撒謊侧蘸，要點面子，但我爸就堅決不同意鹉梨，就是得說真的讳癌。
我真覺得，這是一個好習慣存皂。
一個連自己弱點都無法正視的人晌坤，又談何奮發(fā)去改變這些弱點呢？
哎旦袋，想說的還有好多骤菠，我還是很懷念英國的日子，真的太美好了猜憎。
有機會娩怎，我一定要把那些寫成一篇文章搔课，發(fā)在這里胰柑。QQ空間實在是不太好意思發(fā)文章了，否則別人會覺得我又情緒泛濫了爬泥。
奈何柬讨，我就是個情緒泛濫的人。這算不算袍啡，不敢正視自己的弱點踩官。
哈哈，我覺得境输，根本不算蔗牡。
對了，給那個美國朋友寫去的郵件還沒回，不正常根蟹。估計是給我里面一段描寫我對資本主義理解的文章所激怒了吧姑裂。哈哈。希望不是黔攒。還想著感恩節(jié)去他家做客呢趁啸。
**
總結：遞歸，Array, 如何保證遞歸中ArrayList的統(tǒng)一性督惰。
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (n <= 0 || k <= 0 || k > n) {
            return ret;
        }
        helper(1, k, n, ret, new ArrayList<Integer>());
        return ret;
    }
    
    private void helper(int begin, int k, int n, List<List<Integer>> ret, List<Integer> group) {
        if (group.size() > k) {
            return;
        }
        else if (group.size() == k) {
            ret.add(new ArrayList<Integer>(group));
            return;
        }
        else {
            if (begin > n) {
                return;
            }
            else {
                for (int i = begin; i <= n; i++) {
                    group.add(i);
                    helper(i + 1, k, n, ret, group);
                    group.remove(group.size() - 1);
                }
            }
        }
    }
}

差不多的做法不傅。

Combination 還有一種更高效的解法：

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (k < 0 || k > n) {
            return ret;
        }
        else if (k == 0) {
            ret.add(new ArrayList<Integer>());
            return ret;
        }
        else {
            ret = combine(n - 1, k - 1);
            for (List<Integer> list : ret) {
                list.add(n);
            }
            
            ret.addAll(combine(n - 1, k));
            return ret;
        }
     }
}

復雜度應該都在 O(n!) 左右。
這個做法的思想就是赏胚。
對于一個數(shù)访娶，他只有兩種情況：
要么在 combination 中，
要么不在栅哀。

combine(n - 1, k - 1) 算出在的情況震肮，然后統(tǒng)一加入 n
combine(n - 1, k) 算出不在的情況，直接插入ret

Anyway, Good luck, Richardo! -- 08/06/2016