原文:
给定一个自然数 n ，打印集合的所有子集，不使用任何数组或循环(只允许使用递归)。 例:
input : n = 4
output : { 1 2 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 2 }
{ 1 3 4 }
{ 1 3 }
{ 1 4 }
{ 1 }
{ 2 3 4 }
{ 2 3 }
{ 2 4 }
{ 2 }
{ 3 4 }
{ 3 }
{ 4 }
{ }
input : n = 2
output : { 1 2 }
{ 1 }
{ 2 }
{ }
进场:
- 从开始到 0。
- 考虑带有 n 位的数的二进制表示。
- 从代表 1 的最左边一位开始，第二位代表 2，以此类推，直到代表 n 的第n 位。
- 如果设置了位，则打印该位对应的数字。
- 对 num 的所有值执行上述步骤，直到等于 0。
让我们通过一个例子来理解上面的方法: 考虑输入 n = 4，从开始。
以此类推……直到 num = 0。 以下是上述方法的实现:
c
// c code to print all subsets
// of {1, 2, 3, n} without using
// array or loop, just recursion.
#include
using namespace std;
void subset(int, int, int);
// this recursive function calls subset
// function to print the subsets one by one.
// numbits --> number of bits needed to
// represent the number (simply input value n).
// num --> initially equal to 2 ^ n - 1 and
// decreases by 1 every recursion until 0.
void printsubsets(int numofbits, int num)
{
if (num >= 0)
{
cout << "{ ";
// print the subset corresponding to
// binary representation of num.
subset(numofbits - 1, num, numofbits);
cout << "}" << endl;
// call the function recursively to
// print the next subset.
printsubsets(numofbits, num - 1);
}
else
return;
}
// this function recursively prints the
// subset corresponding to the binary
// representation of num.
// nthbit --> nth bit from right side
// starting from n and decreases until 0
void subset(int nthbit, int num, int numofbits)
{
if (nthbit >= 0)
{
// print number in given subset only
// if the bit corresponding to it
// is set in num.
if (num & (1 << nthbit))
{
cout << numofbits - nthbit << " ";
}
// check for the next bit
subset(nthbit - 1, num, numofbits);
}
else
return;
}
// driver code
int main()
{
int n = 4;
printsubsets(n, pow(2, n) - 1);
}
// this code is contributed by
// sanjeev2552
java 语言(一种计算机语言，尤用于创建网站)
// java code to print all subsets
// of {1, 2, 3, n} without using
// array or loop, just recursion.
class gfg
{
// this recursive function calls subset
// function to print the subsets one by one.
// numbits --> number of bits needed to
// represent the number (simply input value n).
// num --> initially equal to 2 ^ n - 1 and
// decreases by 1 every recursion until 0.
static void printsubsets(int numofbits, int num)
{
if (num >= 0)
{
system.out.print("{ ");
// print the subset corresponding to
// binary representation of num.
subset(numofbits - 1, num, numofbits);
system.out.println("}");
// call the function recursively to
// print the next subset.
printsubsets(numofbits, num - 1);
} else
return;
}
// this function recursively prints the
// subset corresponding to the binary
// representation of num.
// nthbit --> nth bit from right side
// starting from n and decreases until 0.
static void subset(int nthbit, int num, int numofbits)
{
if (nthbit >= 0)
{
// print number in given subset only
// if the bit corresponding to it
// is set in num.
if ((num & (1 << nthbit)) != 0)
{
system.out.print(numofbits - nthbit " ");
}
// check for the next bit
subset(nthbit - 1, num, numofbits);
} else
return;
}
// driver code
public static void main(string[] args)
{
int n = 4;
printsubsets(n, (int) (math.pow(2, n)) -1);
}
}
// this code is contributed by laststringx
python 3
# python3 code to print all subsets
# of {1, 2, 3, …n} without using
# array or loop, just recursion.
# this recursive function calls subset
# function to print the subsets one by one.
# numbits --> number of bits needed to
# represent the number (simply input value n).
# num --> initially equal to 2 ^ n - 1 and
# decreases by 1 every recursion until 0.
def printsubsets(numofbits, num):
if num >= 0:
print("{", end = " ")
# print the subset corresponding to
# binary representation of num.
subset(numofbits-1, num, numofbits)
print("}")
# call the function recursively to
# print the next subset.
printsubsets(numofbits, num-1)
else:
return
# this function recursively prints the
# subset corresponding to the binary
# representation of num.
# nthbit --> nth bit from right side
# starting from n and decreases until 0.
def subset(nthbit, num, numofbits):
if nthbit >= 0:
# print number in given subset only
# if the bit corresponding to it
# is set in num.
if num & (1 << nthbit) != 0:
print(numofbits - nthbit, end = " ")
# check for the next bit
subset(nthbit-1, num, numofbits)
else:
return
# driver code
n = 4
printsubsets(n, 2**n - 1)
c
// c# code to print all subsets
// of {1, 2, 3, n} without using
// array or loop, just recursion.
using system;
class gfg
{
// this recursive function calls subset
// function to print the subsets one by one.
// numbits --> number of bits needed to
// represent the number (simply input value n).
// num --> initially equal to 2 ^ n - 1 and
// decreases by 1 every recursion until 0.
static void printsubsets(int numofbits, int num)
{
if (num >= 0)
{
console.write("{ ");
// print the subset corresponding to
// binary representation of num.
subset(numofbits - 1, num, numofbits);
console.writeline("}");
// call the function recursively to
// print the next subset.
printsubsets(numofbits, num - 1);
} else
return;
}
// this function recursively prints the
// subset corresponding to the binary
// representation of num.
// nthbit --> nth bit from right side
// starting from n and decreases until 0.
static void subset(int nthbit, int num, int numofbits)
{
if (nthbit >= 0)
{
// print number in given subset only
// if the bit corresponding to it
// is set in num.
if ((num & (1 << nthbit)) != 0)
{
console.write(numofbits - nthbit " ");
}
// check for the next bit
subset(nthbit - 1, num, numofbits);
} else
return;
}
// driver codem
public static void main(string[] args)
{
int n = 4;
printsubsets(n, (int) (math.pow(2, n)) -1);
}
}
// this code is contributed by srathore
java 描述语言
output:
{ 1 2 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 2 }
{ 1 3 4 }
{ 1 3 }
{ 1 4 }
{ 1 }
{ 2 3 4 }
{ 2 3 }
{ 2 4 }
{ 2 }
{ 3 4 }
{ 3 }
{ 4 }
{ }
时间复杂度:
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
