【算法】一个没有顺序且不重复的数组的全部组合,全排列:回溯算法、交换算法


/**
 * 转载自:https://blog.csdn.net/weixin_43840202/article/details/113663169
 * @param nums
 * @returns {[]}
 */
// 回溯算法,dfs
let permute = nums => {
    // res储存所有组合系列
    let res = []
    dfs([])
    function dfs(path) {
        console.log('path:', path, 'nums:', nums)
        // 走到最底下(单个全排列完)还未被回溯舍去,表示通过,放入res
        if (path.length === nums.length) {
            console.log('推入res', path)
            return res.push([...path])
        }
        for (let i = 0; i < nums.length; i++) {
            // 回溯,找父级以上是否有当前相同节点,有就舍去
            console.log('判断', path, nums[i])
            if (path.includes(nums[i])) {
                console.log('跳出', path, path.includes(nums[i]))
                continue
            } else {
                console.log('path 里没有 ↓', path, path.includes(nums[i]))
            }
            // 没有相同节点,将他放入path继续往下组合
            console.log('path before', path)
            path.push(nums[i])
            console.log('path after 递归', path)
            dfs(path)
            // 回退上一级 选择另外一个节点进行继续往下
            console.log('pop before', path)
            path.pop()
            console.log('pop after', path)
        }
    }
    return res
}
let result = permute(['0','1'])
console.log(result)

// function permute2(nums) {
//     // 储存所有集合系列
//     let res = []
//
//     // 交换两个元素的值
//     function swap(p, q) {
//         if (p === q) {
//             return
//         }
//         [nums[p], nums[q]] = [nums[q], nums[p]]
//     }
//
//     function dfs(p, q) {
//         // 到了最底层
//         if (p === q) {
//             res.push([...nums])
//             return
//         }
//         // 挨个段进行交换  dfs  交换
//         for (let i = p; i <= q; i++) {
//             swap(p, i)
//             dfs(p + 1, q)
//             swap(p, i)
//         }
//     }
//
//     dfs(0, nums.length - 1)
//     return res
// }
//
// let result2 = permute2([1, 2, 3])
// console.log(result2)

回溯算法执行顺序打印及核心代码:
Snipaste_2021-04-02_13-29-24.png

声明:麋鹿与鲸鱼|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【算法】一个没有顺序且不重复的数组的全部组合,全排列:回溯算法、交换算法


Carpe Diem and Do what I like