我在 LinkedIn 群组上看到这个面试问题 here
总结一下,如果我有一个数组
[1,2,3,4,5]
并输入
3
我需要输出
[1,2,3], [3,2,1], [2,3,1], [2,1,3], [1,3,2], [3,1,2], [2,3,4], [4,3,2],...
排名不分先后。
我一直在想这个问题。我想出了各种不同的解决方法,但所有方法都使用 for 循环。
我认为很明显,为了消除循环,它必须是递归的。
我以为我已经接近于递归地对数组进行分区并连接元素,但非常沮丧,我最终需要另一个 for 循环。
我开始认为这是不可能的(这是不可能的,否则为什么面试问题?)。
有任何想法或链接吗?可能的输出量应该是 5PN,其中 N 是输入。
最佳答案
以下递归算法将尝试打印 {1,.., n} 的每个子集。这些子集通过以下双射与 0 和 2^n-1 之间的数字一对一:对于 0 和 2^n-1 之间的整数 x,如果 x 的第一位设置为,则关联包含 1 的集合one, 2 如果 x 的第二位设置为 1, ..
void print_all_subsets (int n, int m, int x) {
if (x==pow(2,n)) {
return;
}
else if (x has m bits set to one) {
print the set corresponding to x;
}
print_all_subsets(n,m,x+1);
}
您需要使用 n = 5(在您的情况下)、m=3(在您的情况下)和 x = 0 来调用它。
然后您需要实现两个函数“打印对应于 x 的集合”和“x 将 m 位设置为 1”而不使用 for 循环...但这很容易再次使用递归完成。
但是,我认为这更具挑战性——完全消除 for 循环没有意义,有意义的是以巧妙的方式使用它们。
关于arrays - 在没有 for 循环的情况下查找数组的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30509702/