题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List[HTML_REMOVED] res = new ArrayList<>();
dfs(1, n, 0, new int[m], res); // 这里用的 new int[] 没用list 觉得更快用int[]

    /*for (int i = 0; i < 1 << n; i++) {  iterative 方法其实更简单
        int count = Integer.bitCount(i);
        if (count != m) continue;
        int[] temp = new int[m];
        int index = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j & 1) != 0) temp[index++] = j + 1;
        }
        list.add(temp);
    }*/

    for (int[] nums: res) {
        for (int i : nums) {
            System.out.print(i);
            System.out.print(' ');
        }
        System.out.println();
    }
}

public static void dfs(int pos, int n, int index, int[] temp, List<int[]> res) {
    if (index == temp.length) {
        res.add(temp.clone());
        return;
    }
    for (int i = pos; i <= n + 1 + index - temp.length ; i++) { // 这里用了int[] 来存当前结果所以需要剪枝（同时也更快）
    //   当前temp理由 index个元素 还需要找 temp.length - index个元素  从i开始到 n共有n - i + 1个元素可以选 要使得可以满足条件
    // 需要 temp.length - index <= n - i + 1   i <= n + 1 - temp.length + index 
        temp[index] = i;
        dfs(i + 1, n, index + 1, temp, res);
    }
}

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla