77. 组合

题意：

解题思路：

思路：DFS深度优先搜索[回溯]，具体过程看图示；

图示：

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    public $res = [];
    function combine($n, $k) {
        $this->dfs([], $n, $k, 1);
        return $this->res;
    }
    function dfs($array, $n, $k, $start) {
        if ($k == 0) {
            array_push($this->res, $array);
            return;
        }
        for ($i = $start; $i <= $n; $i++) {
            array_push($array, $i);
            $this->dfs($array, $n, $k - 1, $i + 1);
            array_pop($array);
        }
    }
}

GO代码实现：

var res [][]int
func combine(n int, k int) [][]int {
    res = [][]int{}
    var mapT []int
    dfs(mapT, n, k, 1)
    return res
}
func dfs(t []int, n int, k int, start int) {
    if 0 == k {
        s := make([]int, len(t))
        copy(s, t)
        res = append(res, s)
        return 
    }
    for i := start; i <= n-k+1; i++ {
        t = append(t, i)
        dfs(t, n, k - 1, i + 1)
        t = t[:len(t)-1]
    }
}