字符串的全部子序列(递归)

砖业洋__

发布于 2023-05-06 16:54:03

4620

发布于 2023-05-06 16:54:03

文章被收录于专栏：博客迁移同步博客迁移同步

扩展：子序列和子串....

比如“abc”的子串有“”（空串），"a", "b", "c", "ab", "bc", "abc"，共7个，子串个数n(n+1)/2+1，用3*4/2+1也可以算出来为7

但是没有ac，不是相邻的，ac属于子序列，子序列个数计算是2^n

"abc"子序列为""（空串），"a", "b", "c", "ab", "ac", "bc", "abc"，一共2^3=8个

又比如"ABCDEF"的子序列个数为2^6=64个

打印一个字符串的全部子序列，包括空字符串

输入：

abc

输出： // 第一个是空串 c b bc a ac ab abc

import java.io.BufferedInputStream;
import java.util.Scanner;

public class test {

    public static void printAllSub(char[] str, int i, String res) {
        if (i == str.length) {
            System.out.println(res);
            return ;
        } else {
            printAllSub(str, i + 1, res); // 不要下标为i+1的字符
            printAllSub(str, i + 1, res+str[i]); // 要第i+1个字符
        }
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        String str = cin.next();
        printAllSub(str.toCharArray(), 0, "");
        cin.close();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除

cin