字符串的排列

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

1、回溯 穷举

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
    const result = []
    function backtrace(str,selected){
        if(str.length===s.length) {
            result.push(str)
            return
        }
        for(let i=0;i<s.length;i++){
            if(selected[i]) continue
            selected[i] = 1
            backtrace(str+s[i],selected)
            selected[i] = 0
        }
    }

    backtrace('',[])

    return result
};

2、全排列 （可参考下一个排列题解）

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
    let arrs = Array.from(s).sort()
    const result = [arrs.join('')]
    if(arrs.length===1) return result
    while (true) {
        for (let i = arrs.length-2; i >= 0; i--) {
            let next = false
            // 从后往前找非降序的数
            if (arrs[i] < arrs[i + 1]) {
                for (let j = arrs.length - 1; j > i; j--) {
                    if (arrs[j] > arrs[i]) {
                        // 交换
                        swap(arrs, i, j)
                        // 反转后续元素
                        reverse(arrs, i + 1, arrs.length - 1)
                        result.push(arrs.join(''))
                        next = true
                        break
                    }
                }
            } else {
                if (i === 0) {
                    return result
                }
            }
            if(next) break
        }
    }

    function reverse(arr, i, j) {
        while (i < j) {
            swap(arr, i, j)
            i++
            j--
        }
    }
    function swap(arr, i, j) {
        let temp = arr[j]
        arr[j] = arr[i]
        arr[i] = temp
    }
};