面试题08.08 有重复字符串的排列组合

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

 输入：S = "ab"
 输出：["ab", "ba"]

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function(S) {
    let result = []
    const dfs = (path,S) => {
        if(S === '') {
            result.push(path)
            return 
        }
        for(let i=0;i<S.length;i++) {
            if(i>0 && S[i-1] === S[i]) continue // 如果该元素和上一次遍历的元素重复则跳过
            path += S[i]
            dfs(path,S.slice(0,i).concat(S.slice(i+1)))
            path = path.slice(0,path.length -1)
        }
    }
    dfs('',S.split('').sort().join(''))
    return result
};

有重复数字的所有排列

输入：[1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]

function permuteUnique( num ) {
    // write code here
    num.sort((a,b) => a-b)
    let res = []
    let dfs = (tmp,num) => {
        if(num.length === 0) {
            res.push(tmp.slice())
            return
        }
        for(let i=0;i<num.length;i++) {
            if(num[i-1]===num[i]) continue;
            tmp.push(num[i])
            dfs(tmp,num.slice(0,i).concat(num.slice(i+1)))
            tmp.pop()
        }
    }
    dfs([],num)
    return res
}

面试08.07 无重复字符串的排列组合

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function(S) {
    let result = []
    const dfs = (path,S) => {
        if(S === '') {
            result.push(path)
            return 
        }
        for(let i=0;i<S.length;i++) {
            path += S[i]
            dfs(path,S.slice(0,i).concat(S.slice(i+1)))
            path = path.slice(0,path.length -1)
        }
    }
    dfs('',S)
    return result
};

没有重复项数字的所有排列

function permute( num ) {
    // write code here
    let res = []
    let dfs = (tmp,num) => {
        if(num.length === 0) {
            res.push(tmp.slice())
            return
        }
        for(let i=0;i<num.length;i++) {
            tmp.push(num[i])
            dfs(tmp,num.slice(0,i).concat(num.slice(i+1)))
            tmp.pop()
        }
    }
    dfs([],num)
    return res
}