package com.jiucaiyuan.net.question;



import java.util.ArrayList;

import java.util.List;



/**

 * 【问题】打印一个字符串的全部子序列，包含空字符串

 * 【思路】从第一个字符开始，逐个字符进行处理，每个字符都可以选择要还是不要，分两条路递归

 *

 * @Author jiucaiyuan  2022/4/20 23:57

 * @mail services@jiucaiyuan.net

 */



public class PrintAllSubSequence {

    /**

     * 使用数组本身，最后还原

     *

     * @param str

     */

    public static void printAllSubSequence(String str) {

        char[] chs = str.toCharArray();

        process(chs, 0);

    }



    /**

     * 当前来到i这个位置，要和不要，走两条路，

     * 使用数组本身，最后还原

     *

     * @param chs 之前的选择所形成的的结果

     * @param i   当前这个位置

     */

    private static void process(char[] chs, int i) {

        if (i == chs.length) {

            printArray(chs);

            return;

        }

        process(chs, i + 1); //要当前i的字符

        char temp = chs[i];

        chs[i] = 0;

        process(chs, i + 1); //不要当前i的字符

        chs[i] = temp;

    }



    /**

     * 费额外空间

     *

     * @param str

     */

    public static void function(String str) {

        char[] chs = str.toCharArray();

        process(chs, 0, new ArrayList<Character>());

    }



    /**

     * 走到当前i的位置，包含要和不要两条路

     * 费额外空间

     *

     * @param chs chs 所有字符

     * @param i   处理当前i位置的字符

     * @param res 之前的选择

     */

    private static void process(char[] chs, int i, List<Character> res) {

        if (i == chs.length) {

            printList(res);

            return;

        }

        List<Character> resKeep = copyList(res);

        resKeep.add(chs[i]);

        process(chs, i + 1, resKeep);

        List<Character> resNoInclude = copyList(res);

        process(chs, i + 1, resNoInclude);

    }



    private static List<Character> copyList(List<Character> res) {

        List<Character> result = new ArrayList<>();

        for (Character ch : res) {

            result.add(ch);

        }

        return result;

    }



    private static void printArray(char[] chs) {

        for (char ch : chs) {

            if (0 != ch) {

                System.out.print(ch);

            }

        }

        System.out.println();

    }



    private static void printList(List<Character> res) {

        for (char ch : res) {

            if (0 != ch) {

                System.out.print(ch);

            }

        }

        System.out.println();

    }



    public static void main(String[] args) {

        String str = "abc";

        printAllSubSequence(str);

        function(str);

    }

}