回溯法實現全排序Ⅰ

• 2022 年 10 月 2 日
• 筆記
• 數據結構與算法

給定一個不含重複數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：
輸入：nums = [1]
輸出：[[1]]

存放於數組A的n個元素，生成其排列：

1. 第一個元素不動，生成後面n-1個元素的排列；
2. 第一、第二個元素互換，生成後面n-1個元素的排列；
3. 最後，第一個、第n個元素互換，生成後面n-1個元素的排列

為生成後面n-1個元素的排列，繼續採取下面的步驟：

1. 第二個元素不動，生成後面n-2個元素的排列；
2. 第二、第三個元素互換，生成後面n-2個元素的排列；
3. 最後，第二個、第n個元素互換，生成後面n-2個元素的排列；

當排列的前n-2個元素已確定後，為生成後面2個元素的排列，可以：

1. 第n-1個元素不動，生成後面1個元素的排列，此時，n個元素已構成排列；

2. 第n-1、第n個元素互換，生成後面1個元素的排列，此時，n個元素已構成排列；

Java代碼

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有數都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 動態維護數組
            Collections.swap(output, first, i);
            // 繼續遞歸填下一個數
            backtrack(n, output, res, first + 1);
            // 撤銷操作
            Collections.swap(output, first, i);
        }
    }
}

注:

(1)以下是java.util.Collections.swap()方法的聲明。

public static void swap(List<?> list,int i,int j)

參數

• ​ list– 在該列表中的調劑元素。
• ​ i– 要交換的一個元素的索引。
• ​ j– 要交換的其它元素的索引。

(2)

軟件維護主要是指根據需求變化或硬件環境的變化對應用程序進行部分或全部的修改

C++代碼

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有數都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 動態維護數組
            swap(output[i], output[first]);
            // 繼續遞歸填下一個數
            backtrack(res, output, first + 1, len);
            // 撤銷操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

以上代碼轉自力扣題解。筆者自己畫圖總結出來的解析。