二进制枚举

举一个具体的例子，对于给定的字符串"abcde"，我们需要得到由这个字符串的字符组成的所有的子序列。（子序列可以不连续），整个二进制枚举的过程可以参考下面视频。
递归版写法
时间复杂度分析
每一个字符都有两种情况：选择/不选择，因此总的时间复杂度为$O(2^n)$
C++
#include<bits/stdc++.h>
using namespace std;
vector<string>res;
string s;
int n;
void dfs(int u,string t){
    if(u==n){
        if(t.size()>0){
            res.push_back(t);
        }
        return;
    }
    dfs(u+1,t);  //不选择第u个字符
    dfs(u+1,t+s[u]);  //选择第u个字符
}
int main(){
    cin>>s;
    n=s.size();
    dfs(0,"");
    sort(res.begin(),res.end());  //对于所有的子序列，按照字典序升序排列
    for(auto &str:res){
        cout<<str<<endl;
    }
    return 0;
}
Java
import java.util.*;

public class Main {
    static List<String> res = new ArrayList<>();
    static String s;
    static int n;

    public static void dfs(int u, String t) {
        if (u == n) {
            if (!t.isEmpty()) {
                res.add(t);
            }
            return;
        }
        dfs(u + 1, t);  // 不选择第u个字符
        dfs(u + 1, t + s.charAt(u));  // 选择第u个字符
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        n = s.length();
        dfs(0, "");
        Collections.sort(res);  // 对于所有的子序列，按照字典序升序排列
        for (String str : res) {
            System.out.println(str);
        }
    }
}
Python
s = input()
n = len(s)
res = []

def dfs(u, t):
    if u == n:
        if t:
            res.append(t)
        return
    dfs(u + 1, t)  # 不选择第u个字符
    dfs(u + 1, t + s[u])  # 选择第u个字符

dfs(0, "")
res.sort()  # 对于所有的子序列，按照字典序升序排列
for str in res:
    print(str)
迭代版写法
时间复杂度分析
外层循环枚举所有状态，总共有$2^n-1$种状态
内层循环需要枚举每个状态的每一位是否为1，总共有$n$位。
总的时间复杂度为$O(n\times 2^n)$
由于$n\le 20$，因此有$O(n\times 2^n)\le O(20\times 2^{20})\approx 2\times 10^7$
C++
#include<bits/stdc++.h>
using namespace std;
vector<string>res;
string s;
int n;

int main(){
    cin>>s;
    n=s.size();
    for(int state=1;state<(1<<n);state++){  //枚举1~2^n-1的所有状态
        string t;
        for(int i=0;i<n;i++){  //判断第i个字符是否被选择
            if(state>>i&1){  //如果第i个字符被选择
                t.push_back(s[i]);
            }
        }
        res.push_back(t);
    }
    sort(res.begin(),res.end()); //对于所有的子序列，按照字典序升序排列
    for(auto &str:res){
        cout<<str<<endl;
    }
    return 0;
}
Java
import java.util.*;

public class Main {
    static List<String> res = new ArrayList<>();
    static String s;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        n = s.length();
        for (int state = 1; state < (1 << n); state++) {  // 枚举1~2^n-1的所有状态
            StringBuilder t = new StringBuilder();
            for (int i = 0; i < n; i++) {  // 判断第i个字符是否被选择
                if ((state >> i & 1) == 1) {  // 如果第i个字符被选择
                    t.append(s.charAt(i));
                }
            }
            res.add(t.toString());
        }
        Collections.sort(res);  // 对于所有的子序列，按照字典序升序排列
        for (String str : res) {
            System.out.println(str);
        }
    }
}
Python
s = input()
n = len(s)
res = []

for state in range(1, 1 << n):  # 枚举1~2^n-1的所有状态
    t = ""
    for i in range(n):  # 判断第i个字符是否被选择
        if state >> i & 1:  # 如果第i个字符被选择
            t += s[i]
    res.append(t)

res.sort()  # 对于所有的子序列，按照字典序升序排列
for str in res:
    print(str)