全排列问题（深度优先遍历+回溯）

把给定数组中的元素进行全排列LC104

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> out;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        out = new ArrayList<ArrayList<Integer>>();
        if(num.length < 1){
            return out;
        }
        ArrayList<Integer> al = new ArrayList<Integer>();
        dfs(num,al);
        return out;
    }
    //第一种方式，但是不能解决重复问题
    public void dfs(int[] num,ArrayList<Integer> al){
        if(al.size() == num.length){
            out.add(new ArrayList<Integer>(al));
            return;
        }
        for(int i = 0; i < num.length;i++){
            if(!al.contains(num[i])){
                al.add(num[i]);
                dfs(num,al);
                al.remove(al.size()-1);
            }
        }
    }
    //第二种方式
    public static void permutation(int[] num,int i){
        if(i == num.length){
            StringBuffer sb = new StringBuffer();
            for(int j: num){
                sb.append(j);
            }
            System.out.println(sb);
            return;
        }
        for(int j = i; j < num.length;j++){
            int temp = num[j];
            num[j] = num[i];
            num[i] = temp;
            permutation(num,i+1);
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }
}


        //第三种方式
        public static ArrayList<ArrayList<Integer>> permute(int[] arr){
        ArrayList<ArrayList<Integer>> out = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> al = new ArrayList<>();
        boolean[] flag = new boolean[arr.length];
        dfs(arr,al,flag,out);
        return out;
    }
    public static void dfs(int[] arr,ArrayList<Integer> al,boolean[] flag,ArrayList<ArrayList<Integer>> out){
        if(al.size() == arr.length){
            out.add(new ArrayList<Integer>(al));
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < al.size(); i++) {
                sb.append(al.get(i)+" ");
            }
            System.out.println(sb);
            return;
        }
        for(int i = 0;i < arr.length;i++){
            if(flag[i] == false){
                flag[i] = true;
                al.add(arr[i]);
                dfs(arr,al,flag,out);
                flag[i] = false;
                al.remove(al.size()-1);
            }
        }
    }

多个元素的全排列LC131

给出一个仅包含数字的字符串，给出所有可能的字母组合。
数字到字母的映射方式如下:(就像电话上数字和字母的映射一样)

Input:Digit string "23"
Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

import java.util.*;

public class Solution {
    /**
     *
     * @param digits string字符串
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> letterCombinations (String digits) {
        // write code here
        if(digits.length() ==0){
            res.add("");
            return res;
        }

        String s[] = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        dfs(s,new StringBuilder(),digits,0);
        return res;
    }

    public void dfs(String[] s,StringBuilder sb,String digits,int begin){
        if(begin == digits.length()){
            res.add(sb.toString());
            return;
        }
        //获取此时数字代表的字符串：如果为2，则为abc
        String str = s[Character.getNumericValue(digits.charAt(begin))];
        for(char c: str.toCharArray()){
            sb.append(c);
            dfs(s,sb,digits,begin+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}