<?php

function getMsectime() {
    list($msec, $sec) = explode(' ', microtime());
    return (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
}

class Solution {

    private $path = []; // 一个组合
    private $data = []; // 所有结果
    /**
     * 77. 组合
     * 
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     * 示例:
     * 输入: n = 4, k = 2
     * 输出:
     * [
     *   [2,4],
     *   [3,4],
     *   [2,3],
     *   [1,2],
     *   [1,3],
     *   [1,4],
     * ]
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    function combine($n, $k) {
        $this->combineBackTracking($n, $k, 1);
        return $this->data;
    }

    function combineBackTracking($n, $k, $start) {
        if (count($this->path) == $k) {
            $this->data[] = $this->path;
            // $this->path = [current($this->path)];
            // var_dump($this->path);
            // $this->path = [];
            return false;
        }

        for ($i = $start; $i <= $n; $i++) {
            // 结果放进数组
            // array_push($this->path, $i);
            $this->path[] = $i;
            $this->combineBackTracking($n, $k, $i+1);
            // 得到结果后，将按递归依次弹出，重新开始下一层搜索
            array_pop($this->path);
        }
    }
}

echo "<pre>";


$time1 = getMsectime();
$solution = new Solution;

$result = $solution->combine(4, 2);


$time2 = getMsectime();

$result = (is_object($result) || is_array($result)) ? json_encode($result) : $result;
// echo $solution->nums."次<br>";
// echo '<br>结果：'.implode(',', $result1)."<br>", '执行耗时：'.($time2 - $time1)."ms";
echo '<br>结果：'.$result."<br>", '执行耗时：'.($time2 - $time1)."ms";