문자열의 ?, 0과 1로 치환한 모든 경우의 수 리턴하기

ex ) a?b?c >> a0b0c0 a0b0c1 ...

바로 코딩하겠읍니다..

void printallpermutations(string s, vector<string> & ret, int curr){

// general case

// go through until ? met

for(int i = curr; i < s.size() ; i++){

if(s[curr]=='?'){

s[curr]='0';

printallpermutations(s,ret,curr+1);

s[curr]='1';

printallpermutations(s,ret,curr+1);

return;

}

}

// base case

ret.push_back(s);

return;

}

순회는 "모든" 재귀함수들에 걸쳐 처음 : 1 * a1, 두번째 2* a2 ... 2^N * an 이고 a1+a2... + an = length 이다.

그리고 재귀함수의 총 호출횟수는 2^N+1 회..  , N = ?의 갯수, 대략 length에 비례한다고 생각해도 될 듯

대강 O(2^N) 정도가 아닐까?

space complexity 는 length * 2^N 이겠다.