算法题/排列组合：1到n取k个数的组合

题目

给定两个整数n和k，返回1..n中所有可能的k个数的组合。

示例1：

输入：n=4, k=2
输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
解释：

解答

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是：path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历可能的搜索起点
        for (int i = begin; i <= n; i++) {
            // 向路径变量里添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }
}

JavaScript

function combine(n, k) {
  let res = [];
  if (k <= 0 || n < k) {
    return res;
  }
  
  let path = [];
  dfs(n, k, 1, path, res);
  
  return res;
}

function dfs(n, k, begin, path, res) {
  if (path.length === k) {
    res.push([...path]);
    return;
  }
  
  for (let i = begin; i <= n; i++) {
    path.push(i);
    dfs(n, k, i + 1, path, res);
    path.pop();
  }
}

Python

def combine(n, k):
    res = []
    if k <= 0 or n < k:
        return res

    path = []
    dfs(n, k, 1, path, res)

    return res


def dfs(n, k, begin, path, res):
    if len(path) == k:
        res.append(path[:])
        return

    for i in range(begin, n + 1):
        path.append(i)
        dfs(n, k, i + 1, path, res)
        path.pop()

Go

package main

import (
	"fmt"
)

func combine(n, k int) [][]int {
	res := [][]int{}
	if k <= 0 || n < k {
		return res
	}

	path := []int{}
	dfs(n, k, 1, path, &res)

	return res
}

func dfs(n, k, begin int, path []int, res *[][]int) {
	if len(path) == k {
		temp := make([]int, k)
		copy(temp, path)
		*res = append(*res, temp)
		return
	}

	for i := begin; i <= n; i++ {
		path = append(path, i)
		dfs(n, k, i+1, path, res)
		path = path[:len(path)-1]
	}
}

func main() {
	n := 4
	k := 2
	result := combine(n, k)
	fmt.Println(result)
}