算法Day29 打印数目

打印数目

Description

小硕有一套字母表arr，其中每个上都刻有一个字母arr[i]。返回小硕可以印出的非空字母序列的数目。
注意：本题中，每个字母只能使用一次。

Input

输入字符串arr
1≤arr.length≤7

Output

输出可打印数目

Sample

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;


public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int count = 0;

    public static void main(String[] args) throws IOException {
        String s = reader.readLine();
        ArrayList<Character> choice = new ArrayList<>();
        for(int i = 0;i<s.length();i++){
            choice.add(s.charAt(i));
        }
        Collections.sort(choice);
        backtrack(choice);
        System.out.println(count);
    }
    public static void backtrack(ArrayList<Character> choice){
        char flag = 0;
        for(int i = 0;i<choice.size();i++){
            Collections.sort(choice);
            char c = choice.get(i);
            if(c != flag){
                choice.remove(i);
                count++;
                backtrack(choice);
                choice.add(c);
            }
            flag = c;
        }
    }

}

思路

使用回溯法，与一般对层数迭代不同，这里直接使用数组进入排序，减少了使用全局变量等工作量
每次进行sort排序，是为了将c加入后进入正确的位置，保证恢复现场