<?php

class Solution {


    public $result = [];
    /**
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    function combine($n, $k) {

        if(!$n || !$k){
            return [];
        }

        $this->backTrack($n, $k, 1, []);

        return $this->result;

    }

    function backTrack($n, $k, $step, $path)
    {

        if(count($path) === $k){

            $this->result[] = $path;

            return;

        }
        if($step === $n + 1)
            return;

        //$step不放入解集$path情况
        $this->backTrack ($n, $k, $step + 1, $path);

        //$step放入解集$path情况
        $path[] = $step;

        $this->backTrack($n, $k, $step + 1, $path);

        //还原
        array_pop($path);
    }
}

$model = new Solution();

var_dump($model->combine(4, 2));