当前位置: 代码迷 >> 综合 >> 给一个整数数组,输出所有可能的子集
  详细解决方案

给一个整数数组,输出所有可能的子集

热度:79   发布时间:2024-01-16 18:08:18.0

1:迭代法

思路很简单,就是用一个二进制的数表示当前元素集合的状态,状态的第i位如果是0,说明当前集合没有这个元素;如果是1,就是有这个元素,然后输出。

//动态规划?

int a[4] = { 1, 2, 3, 4 }; int t = 1<<4; for (int i = 1; i <= t - 1; i++) {cout<<"{";for (int j = 0; j <= 4; j++){if ((1 << j)&i)cout << a[j] << " ";}cout << "}" << endl; }

2:递归法

思路也很简单,就是把集合状态用pos数组存下来,pos[i]如果是0,说明当前集合没有这个元素;如果是1,就是有这个元素,然后输出.

//深搜?

void dfs(int a[], int pos[], int now,int len) {if (now == len){cout << "{";for (int i = 0; i < now; i++){if (pos[i] == 1)cout << a[i] << " ";}cout << "}" << endl;return ;}pos[now] = 0;dfs(a, pos, now+1,len);pos[now] = 1;dfs(a, pos, now+1,len); } int main() {int a[4] = {1, 2, 3, 4};int pos[4] = {0, 0, 0, 0};int now = 0;int len = 4;dfs(a, pos, now,len);return 0; }


  相关解决方案