问题描述：
对于固定数组{0,1,2,3,4,5,6,7,8,9}
输入bool数组{0,1,1,1,1,1,1,1,0,0},其中0对应的下标数组元素可出现也可以不出现，1必须出现
出现 所有的可能的组合（组合问题标准的解法是回溯），转化为字符串，并按照字符串升序排序！
|
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> res;
void dfs(int* m, int* n, int index,string ss)
{
while (index<10&&n[index] == 1)
{
ss += string(1, char(m[index] + '0'));
index++;
}
if (index == 10)
{
res.push_back(ss);
return;
}
dfs(m, n, index + 1, ss);
ss += string(1, char(m[index] + '0'));
dfs(m, n, index + 1, ss);
}
int main()
{
int m[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n[10];
for (int i = 0; i < 10; ++i)
cin >> n[i];
dfs(m, n, 0, string());
sort(res.begin(), res.end());
for (int i = 0; i < (int)res.size(); ++i)
cout << res[i] << endl;
return 0;
}
|
搞了半天写了个python实现，用的不熟练
|
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
#a_str = list('0123456789')
a_str = '0123456789'
print type(a_str)
print a_str
res =[]
bool_list = sys.stdin.readline().split()[0]
def dfs(a_str,bool_list,index,tmp):
while index<10 and int(bool_list[index])==1:
tmp += a_str[index]
index +=1
if index ==10:
res.append(tmp)
return
dfs(a_str,bool_list,index+1,tmp)
tmp += a_str[index]
dfs(a_str,bool_list,index+1,tmp)
dfs(a_str,bool_list,0,'')
print 'len:' + str(len(res))
print res
#将字符串转换成数字列表
bool_list =list(bool_list)
print bool_list
bool_list = [int(x) for x in bool_list]
print bool_list
'''上题也可以先将字符串列表转换成int数组，之后就不用再while里强制转换了
|
