组合数 DFS的两种解法哪种更好？求解~

关于leetcode上DFS的一道题目，给一个K，一个N，找出1 - N的所有组合数，个数为K。这题是用DFS来解的，但是目前小弟写出两个DFS解法，我不知道这两个解法 到底是哪个更加好一点。直觉告诉我第一个分支更少，会比较好，但是运行下来 两个相差无几 甚至分之多的那个解法目测更加快一点，有点晕。。求教一下，这到底可以怎么分析？一般做题的时候 哪种更加符合思维呢？

第一个解法的意思就是可以选当前的元素，或者不选。所以两个分支。
第二个解法的意思就是选当前的元素，然后依次选下一个（不选之前的元素了）。所以分支挺多的。

解法附上：

    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> coll = new ArrayList<ArrayList<Integer>>();
        if(n > 0){
            dfs(1, n, k, new ArrayList<Integer>(), coll);
        }
        return coll;
    }


解法一：
    public void dfs(int low, int high, int count, ArrayList<Integer> list ,ArrayList<ArrayList<Integer>> coll){
        if(high - low + 1 < count){
            return;
        }
        if(count == 0){
            coll.add(new ArrayList<Integer>(list));
            return;
        }
        // this element is not selected
        dfs(low + 1, high, count, list, coll);

        // this element is selected
        list.add(low);
        dfs(low + 1, high, count - 1, list, coll);
        list.remove(list.size() - 1);
    }


解法二：
    public void dfs(int low, int high, int count, ArrayList<Integer> list ,ArrayList<ArrayList<Integer>> coll){
        if(high - low  + 1 < count){
            return;
        }
        if(count == 0){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            newList.addAll(list);
            coll.add(newList);
        }
        for(int i = low; i <= high; i++){
            list.add(i);
            dfs(i + 1, high, count - 1, list, coll);
            list.remove(list.size() - 1);
        }
    }

我是用第二种的，我觉得两种都一样吧？

kelvinzhong 发表于 2014-1-7 12:10
我是用第二种的，我觉得两种都一样吧？

貌似递归树不太一样哦
第二个解法具体是怎么理解的呢？ 我的理解就是 选择当前的元素，然后依次选择下一个，之前选过的就当是不选了。每个状态下面就当做有n个vertex需要进行遍历。

我是这么想的，这样理解对吗？

第一种是题解，就是用在这题上的解法。
第二种是数字排列题的通解的变形。

第一种比较思路清晰。
但是面试我会用第二种，因为第二种记住后，可以面对各种衍生问题。 比如：指定数不重复等

readman 发表于 2014-1-7 13:05
第一种是题解，就是用在这题上的解法。
第二种是数字排列题的通解的变形。

确实，相比第一个解法，总觉得第二个解法 很奇怪，递归树画的不清不楚的。还有一种题目就是求出一个数组所有的subsets，也可以用这两种解法做。
对于第二种解法，是不是就可以理解成，每到一个状态，依次遍历它当前所能选择到的元素（这些元素可以当做图论中下一个需要遍历的vertex）
这样的理解是正常的思维吗？

baojialiang 发表于 2014-1-7 14:03
确实，相比第一个解法，总觉得第二个解法 很奇怪，递归树画的不清不楚的。还有一种题目就是求出一个数组所 ...

对的
第二种方法更接近于图论中的

readman 发表于 2014-1-7 15:24
对的
第二种方法更接近于图论中的

嗯啊 不过像求所有subsets的问题，第二种方法的时间复杂度是多少呢？所有子集一共2^n个，
我总觉得如果用第二个方法的话，时间复杂度是n!，因为第一层有n个选择，第二层有n - 1个选择，最后一层只有1个选择，这样的话就是n!的复杂度吧。这样的分析对吗?我想了半天觉得是对的，但又觉得应该是2^n的复杂度。

第二个是2^n。因为每层迭代不会都走完

第二种好理解很多吧，因为combine不讲顺序，所以只能按照一定order取排列，复杂度就是组合数的复杂度，n!/((n-k)!*k!)，你返回的答案有这么多个组合数，复杂度不会小于这个。下面是我的code。
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
                if(k==0){
                        res.add(new ArrayList<Integer>());
                        return res;
                }
                for(int i=n;i>0;i--){
                        for(ArrayList<Integer>list:combine(i-1,k-1)){
                                list.add(i);
                                res.add(list);
                        }
                }
                return res;
    }

readman 发表于 2014-1-9 12:36
第二个是2^n。因为每层迭代不会都走完

嗯 能解释下为什么是2^n吗？ 在subsets这个题里，虽然我知道所有的子集个数是2^n，我也画出了递归树，确实是2^n个状态，但是怎么从递归树上面来分析时间复杂度呢？还是就是因为子集的个数是2^n，才推出复杂度是2^n？
我在下面画了递归树，假设有4个元素，1，2，3，4