[Leetcode] Combinations 組合數(shù)

omgdog 發(fā)布于2019-08-14 12:31 / 2169人閱讀

摘要：回溯法復雜度時間空間思路通過深度優(yōu)先搜索，回溯出所有可能性即可。而遞歸的條件是當或者時，返回一個空列表。注意當返回的是空列表時，要加一個空列表進去，否則循環(huán)會被跳過代碼加入一個空列表，防止跳過循環(huán)

Combinations

Given two integers n and k, return all possible ombinations 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],
]

回溯法 復雜度

時間 O(N) 空間 O(K)

思路

通過深度優(yōu)先搜索，回溯出所有可能性即可。

代碼

public class Solution {
    
    List> res = new ArrayList>();
    
    public List> combine(int n, int k) {
        dfs(1, k, n, new ArrayList());
        return res;
    }
    
    private void dfs(int start, int k, int n, List tmp){
        // 當已經(jīng)選擇足夠數(shù)字時，將tmp加入結(jié)果
        if(k == 0){
            res.add(new ArrayList(tmp));
        }
        // 每一種選擇數(shù)字的可能
        for(int i = start; i <= n; i++){
            tmp.add(i);
            dfs(i + 1, k - 1, n, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

公式法 復雜度

時間 O(N) 空間 O(N)

思路

在數(shù)學中，組合數(shù)有這么一個性質(zhì)
$$ C_{n}^{k}=C_{n-1}^{k-1}cup n+C_{n-1}^{k}$$
所以，我們可以分別求出C(n-1,k-1)和C(n-1,k)，并將前者都加上n，最后將兩個結(jié)果和到一起，就是C(n,k)。而遞歸的Base條件是當n=0,k=0或者n 注意

當C(n-1,k-1)返回的是空列表時，要加一個空列表進去，否則for循環(huán)會被跳過

代碼

public class Solution {
    public List> combine(int n, int k) {
        // Recursion: C(n, k) = C(n-1, k-1) U n + C(n-1, k)
        // Base: C(0, k) C(n, 0) n < k ---> empty
        List> res = new LinkedList>();
        if(n < k || n == 0 || k == 0){
            return res;
        }
        // C(n-1, k-1) U n
        List> temp = combine(n-1, k-1);
        List> part1 = new LinkedList>();
        // 加入一個空列表，防止跳過for循環(huán)
        if(temp.isEmpty()){
            List list = new LinkedList();
            temp.add(list);
        }
        for(List list : temp){
            list.add(n);
            part1.add(list);
        }
        // C(n-1, k)
        List> part2 = combine(n-1, k);
        res.addAll(part1);
        res.addAll(part2);
        return res;
    }
}