ebay 面试 NP问题请教

Hello,

  本人**一位，前几天面了ebay,请教一个题

  给 1 输出 1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

输出所有由小于等于这个数的合集

请问是NP问题么？应该怎么做

这个应该是用dfs可以就可以吧

27个数字里似乎少了一个的样子...
从第一个位置开始，从小到大枚举这个位置的可能数字，然后递归到下一位...
求下面的筒子们指正...

        public static void helper(String s, int n){
                if(s.length()==n){
                        System.out.println(s);
                        return;
                }
                for(int i =1;i<=n;i++){
                helper(s+Integer.toString(i),n);
                }
        }
        这样可以不

楼上Integer.toString多余了  直接 s+i 就可以了

1.     public static void addPrefix(String prefix, int n) {
   
2.         if (prefix.length() == n) {
   
3.             System.out.println(prefix);
   
4.         } else {
   
5.             for (int i = 1; i <= n; i++) {
   
6.                 addPrefix(prefix + i, n);
   
7.             }
   
8.         }
   
9.     }

复制代码

是 NP problem.
给定N,总共有 N^N个组合要输出

这题目是permutations的变体.区别是,在递归处理下一位之前,不需要再检查当前位是否已经组合过了.

1. void dfs(vector<vector<int> > &results, int n, vector<int> & sol){
   
2.     if(sol.size() == n){
   
3.         results.push_back(sol);
   
4.         return ;
   
5.     }
   
6.     for(int i=1; i<=n; i++){
   
7.             sol.push_back(i);
   
8.             dfs(results, n, sol);
   
9.             sol.pop_back();
   
10.     }
    
11. }
    
12. 
    
13. vector<vector<int> > getSets(int n) {
    
14.     vector<vector<int> > results;
    
15.     if(n==0) return results;
    
16.     vector<int> sol;
    
17.     dfs(results, n, sol);
    
18.     return results;
    
19. }

复制代码

感谢各位，自己调试通过了。。。
自己真是水平低啊
需要继续努力