输出一个字符串的全部子序列--java

太过爱你忘了你带给我的痛 2022-10-07 01:54 91阅读 0赞

描述：

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

比如："abc"

输出结果：

c  
 b  
 bc  
 a  
 ac  
 ab  
 abc

=========

1、实现方案：通常采用递归的思路来解决。

2、分析：str 固定字符串参数 ，到了str\[index\]字符，index是位置，str\[0..index-1\]已经走过了！之前的决定，都在path上，并且已经不能改变了。str\[index....\]还能决定，之前已经确定，而后面还能自由选择的话，把所有生成的子序列，放入到ans里去。

3、核心代码：

public class NanDaoPrintAllSubs {
    
        public static void main(String[] args) {
            String test = "abc";
            List<String> ans1 = subList(test);
    
            //如果打印非重复子序列，可用数据结构
           // HashSet<String> ans1 = new HashSet<>();
            for(String ans :  ans1){
                System.out.println(ans);
            }
            System.out.println("=========");
        }
    
        private static List<String> subList(String test) {
            //转换成字符数组
            char[] str = test.toCharArray();
            String path = " ";
            List<String> ans = new ArrayList<>();
            process(str,0,ans,path);
            return ans;
    
        }
    
        private static void process(char[] str, int index, List<String> ans, String path) {
            if(index == str.length){
                // 把所有生成的子序列，放入到ans里去
                ans.add(path);
                return;
            }
            // 没有要index + 1位置的字符
            process(str,index + 1,ans,path);
    
            // 要了index + 1位置的字符
            process(str,index + 1,ans,path + str[index]);
        }
    
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

到此，该算法分析完成，采用递归方案，当然也有其他思路，小伙伴可以尝试一下，定会惊喜多多！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/3b79aace5fc74c8eaf6859481d82c244.png