leetcode刷題/回溯算法 47. 全排列 II

47. 全排列 II

題意

給定一個可包含重複數字的序列

nums

，按任意順序 傳回所有不重複的全排列。

示例 1：

輸入：nums = [1,1,2]
輸出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
           

示例 2：

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

解題思路:

排列 + 去重

問	答
如何去重?	分兩步走,詳細見下文.
遞歸傳回條件	如果路徑長度等于數組長度,就說明找到一種結果.添加并放回
單層遞歸	從0開始周遊整個數組,如果已經周遊過或者是重複的就跳過這一個,尋找滿足條件的遞歸
參數	需要一個标記數組來記錄是否已經用過
剪枝	不需要

遇到這種需要不重複的,我們需要的就是在原來遞歸的基礎上做多兩步.

1. 排序數組,讓相同的數字相鄰
2. 如果在同一層中的非首位數等于後面的數且後面的數等于false(說明已經遞歸過一個相同的數了),就不繼續周遊這個數

代碼

class Solution {
public:
//遞歸回溯
//num是原數組,used是标記位
void backtracking(vector<int> &nums,vector<bool>& used)
{
    //如果長度和nums長度一樣,說明找到一種可能
	if (path.size() == nums.size())
	{
		res.push_back(path);
		return;
	}
    //從0開始周遊整個數組
	for (int i = 0; i < nums.size(); i++)
	{
        //如果目前位已經在路徑中,不需要繼續遞歸,直接跳過
		if (used[i] == true)
			continue;
        //如果不是第一位 && 與後面一位相等 && 後面一位已經被作為起始點被遞歸過了. 就直接跳過.防止重複
		if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
			continue;
        //添加目前值到路徑中
		path.push_back(nums[i]);
        //标記目前位
		used[i] = true;
        //遞歸尋找下一位
		backtracking(nums, used);
        //回溯
		used[i] = false;
		path.pop_back();
	}
}
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    //先排序
    sort(nums.begin(), nums.end());
    //建立一個标記數組
	vector<bool> flag(nums.size(), false);
    //開始遞歸
	backtracking(nums, flag);
	return res;
    }

private:
  vector<vector<int>> res;
  vector<int>path;  
};
           

總結:

在排序的基礎上加上一個去重即可.去重比較巧妙,用到了标記數組.需要想清楚其中的邏輯