47. Permutations II

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)Hash Table (Bảng băm)Bit Manipulation (Thao tác bit)

⏱️ Thời gian O(V+E)

💾 Không gian O(V)

💻 Lời Giải

C++ 0047-permutations-ii.cpp

class Solution {
private:
    vector<int> nums;
    unordered_map<int, int> cnt;
    vector<int> path;
    vector<vector<int>> ans;
    int n;
    
public:
    void dfs() {
        if (path.size() == n) {
            ans.push_back(path);
            return;
        }
        for (auto &[key, _] : cnt) {
            if (cnt[key] > 0) {
                cnt[key]--;
                path.push_back(key);
                dfs();
                path.pop_back();
                cnt[key]++;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        this->nums = nums;
        this->n = nums.size();
        for (int num : nums) {
            cnt[num]++;
        }
        dfs();
        return ans;
    }
};