77. 组合

QSir   in 北京

原题链接 (opens new window)

20240213200950_image.png

20240213201356_image.png

20240213212040_image.png

20240213202921_image.png

20240213210244_image.png


<?php
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    function combine($n, $k) {
        $result = [];
        $this->dfs($n,$k,1,0,[],$result);
        return $result;
    }

    function dfs($n, $k,$start, $level,$path, &$result) {
        if (count($path) == $k) {
            $result[] = $path;
            return;
        }

        for ($i = $start; $i <= $n; $i++) {
						
						# 剪枝 不要也正确
            if($level + ($n - $start + 1) < $k) {
                continue;
            }

            $path[] = $i;
            $this->dfs($n,$k,$i + 1,$level + 1,$path,$result);
            array_pop($path);
        }
    }
		
		function dfs3($n, $k,$start, $path, &$result) {
        if (0 == $k) {
            $result[] = $path;
            return;
        }

        for ($i = $start; $i <= $n; $i++) {

            //if ($start > $n - $k + 1) {
            //    continue;
            //}

            $path[] = $i;
            $this->dfs3($n,$k - 1,$i + 1,$path,$result);
            array_pop($path);
        }
		}

}
//leetcode submit region end(Prohibit modification and deletion)

$s = new Solution();
$ret = $s->combine(4, 3);
print_r($ret);


copy success
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

20240213214931_image.png 20240214160013_image.png

class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    function combine($n, $k) {
        $result = [];
        $this->dfs($n,$k,1,0,[],$result);
        return $result;
    }

    function dfs($n, $k,$start, $level,$path, &$result) {
        if (0 == $k) {
            $result[] = $path;
            return;
        }

        if($start > $n - $k + 1) {
            return;
        }

        //选择 $start
        $path[] = $start;
        $this->dfs($n,$k - 1,$start + 1,$level + 1,$path,$result);
        array_pop($path);
				
        //不选择 $start
        $this->dfs($n,$k,$start + 1,$level + 1,$path,$result);
    }

}


copy success
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34