回溯算法(字符串排列)

  1. 输入："aab"
  3. 返回值：["aab","aba","baa"]
  1. function Permutation(str)
  2. {
  3.     if(!str.length) return []
  4.     let res= [];
  5.     let used=[];
  6.     let dfs = (path="")=> {
  7.         if(path.length==str.length) return res.push(path.slice())
  8.         for(let i=0;i<str.length;i++) {
  9.             if(used[i]) continue
  10.             used[i]=true
  11.             dfs(path+str.charAt(i));
  12.             used[i]=false
  13.         }
  14.     }
  15.     dfs()
  16.     // 去掉重复的字符串
  17.     return Array.from(new Set(res))
  18. }

括号填充

输入：3
输出：["((()))","(()())","(())()","()(())","()()()"]

function generateParenthesis( n ) {
     if(n==0) return []
    let res = []
    let dfs = (LRemain,RRemain,path) => {
        if(path.length==2*n) return res.push(path);
        // 当剩余"("大于0时，添加"("
        if(LRemain>0)  dfs(LRemain-1,RRemain, path+"(")
        // 当剩余")"大于剩余"("时，添加")"
        if(LRemain<RRemain)  dfs(LRemain,RRemain-1, path+")")
    }
    dfs(n-1,n,"(")
    return res
}

解析：括号填充有以下俩特点：

  1. 左边括号需要先用完，要保证先添加左括号
  2. 当左括号数量用多了，需要添加右括号，保证右括号后添加

LRemain>0 -> LRemain>0 -> LRemain LRemainimage.png
LRemain>0 -> LRemain LRemain>0 -> LRemainimage.png