打印数目
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加入后进入正确的位置，保证恢复现场
