题目描述

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<int[]> res = new ArrayList<>();
        //dfs(1, n, 0, new int[m], res);  // 这里用的 new int[] 没用list 觉得更快用int[] 


        /*for (int i = 0; i < 1 << n; i++) {  //iterative 方法其实更简单  但是不逆序的话似乎无法按照字典序
 // 比如 n = 5  m = 3      1 2 3(00111 = 7)   1 2 4(01011 = 11)     1 3 4(01101 = 13)   2 3 4(01110 = 14)   1 2 5(10011 = 19)
 // 我们可以看到 如果按照字典序 1 2 5必然在 1 3 4   2 3 4后面但是没有按照字典序只要输出就好了 所以错误 要逆过来 
 // backtrack自然可以顺序 因为从第一个开始找 一直是往后面找的 
            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; // 因为j是从0 - n - 1 要对应1 - n 所以要记得j + 1
            }
            res.add(temp);
        } */

        for (int i = (1 << n) - 1; i >= 0; i--) { // 这样反过来就可以字典序了 对应关系我也写在下面了 
            if (Integer.bitCount(i) != m) continue;
            int[] temp = new int[m];
            int index = 0;
            for (int j = n - 1; j >= 0; j--) {   //  n - 1 to 1    n - 2  to  2     0 to n
                if ((i >> j & 1) != 0) temp[index++] = n - j;
            }
            res.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);
        }
    }
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla