AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 93. 【java】递归实现组合型枚举    原题链接    简单

作者: 作者的头像   tt2767 ,  2019-12-08 00:45:06 ,  阅读 335


1


// 需要反复取的时候才要循环判断,只向后取直接把状态传下去就可以了
// 不需要所有状态空间,所以可以剪枝

import java.util.*;
import java.util.stream.*;

public class Main{

    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();
        dfs(0, n, m, 0, 0);
    }

    void dfs(int start, int n, int m, int sum, int status){
        if (sum == m ){
            buffer.clear();
            for (int i = 0 ; i < n ;i ++){
                if (((status >> i) & 1) == 1 ){
                    buffer.add(i+1);
                } 
            }
            String res = String.join(" ", buffer.stream().map(String::valueOf).collect(Collectors.toList()));
            System.out.println(res);


        } else if (n - start + sum >= m){
            dfs(start+1, n, m, sum+1, status | (1 << start));
            dfs(start+1, n, m, sum, status);
        }


    }
    private List<Integer> buffer = new ArrayList<>();
    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) throws Exception {new Main().run();}
}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息