给定一个正整数 n,假设序列 S={1,2,3,...,n},求 S的所有子集。n是正整数,范围是1~12 。
时间: 2024-05-12 16:19:18 浏览: 171
这可以使用回溯法来解决。具体地,对于每个元素,我们可以选择将其放入结果集中或不放入。因此,我们可以使用一个递归函数来遍历所有可能的情况。
代码如下:
```python
def subsets(n):
def backtrack(start, path):
res.append(path[:])
for i in range(start, n+1):
path.append(i)
backtrack(i+1, path)
path.pop()
res = []
backtrack(1, [])
return res
n = 3
print(subsets(n)) # 输出 [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
```
在上述代码中,backtrack函数用于递归地遍历所有可能的情况,start表示当前遍历到的元素,path表示当前的路径。当遍历到某个元素时,我们可以选择将其放入路径中,然后递归遍历下一个元素;或者不放入路径中,直接递归遍历下一个元素。对于每个路径,我们都将其加入结果集中。最终返回结果集即可。
阅读全文