Replacing the occurence of the character in string

Given a string (for example: "a?bc?def?g"), write a program to
generate all the possible strings by replacing ? with 0 and 1.

Example:
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.


I have developed a program as shown below but please advise if something more efficiently can be done.

public class ReplaceQuestionMark {
public ArrayList replace(String target){
return replaceHelper(target, target.length()-1);
}

public ArrayList replaceHelper(String target, int to){
char c = target.charAt(to);
if (to == 0){
ArrayList res = new ArrayList();
if (c == '?'){
res.add("0");
res.add("1");
}
else{
res.add(c+"");
}
return res;
}
ArrayList res = new ArrayList();
ArrayList preRes = replaceHelper(target, to-1);
if (c == '?'){
for (String token: preRes){
res.add(token + "0");
res.add(token + "1");
}
}
else{
for (String token: preRes){
res.add(token + c);
}
}
return res;
}

public static void main(String[] args){
ReplaceQuestionMark rqm = new ReplaceQuestionMark();
ArrayList res = rqm.replace("a?b?c?");
for (String s: res){
System.out.println(s);
}
}
}


An easy way to generate all of the possible 0 and 1 combinations is to use binary numbers.

If there are 3 ?'s then the combinations of 0's and 1's will be all binary numbers from 0 to 2^3 - 1:

0:  000
1:  001
2:  010
3:  011
4:  100
5:  101
6:  110
7:  111

So all you need to do is count the number of question mark characters (N) and then count from 0 to 2^N - 1 to generate all the possible 0 and 1 combinations.

Also I notice that half of these strings will have a 0 in the first position, and half will have a 1. I wonder if this feature could be used to reduce the amount of iteration you need to do.

StackExchange Code Review Q#60372, answer score: 6