/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
ja/codes/cpp/chapter_backtracking/permutations_ii.cpp
56 строк
2 KB
Yudong Jin
Re-translate the Japanese version (#1871)
30 мар 2026, 02:30
Не верифицирован
30 мар 2026, 02:30
d7b2277
Код
Авторство
О чём код?
/** * File: permutations_ii.cpp * Created Time: 2023-04-24 * Author: krahets (krahets@163.com) */ #include "../utils/common.hpp" /* バックトラッキング：順列 II */ void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) { // 状態の長さが要素数に等しければ、解を記録 if (state.size() == choices.size()) { res.push_back(state); return; } // すべての選択肢を走査 unordered_set<int> duplicated; for (int i = 0; i < choices.size(); i++) { int choice = choices[i]; // 枝刈り：要素の重複選択を許可せず、同値要素の重複選択も許可しない if (!selected[i] && duplicated.find(choice) == duplicated.end()) { // 試行: 選択を行い、状態を更新 duplicated.emplace(choice); // 選択済みの要素値を記録 selected[i] = true; state.push_back(choice); // 次の選択へ進む backtrack(state, choices, selected, res); // バックトラック：選択を取り消し、前の状態に戻す selected[i] = false; state.pop_back(); } } } /* 全順列 II */ vector<vector<int>> permutationsII(vector<int> nums) { vector<int> state; vector<bool> selected(nums.size(), false); vector<vector<int>> res; backtrack(state, nums, selected, res); return res; } /* Driver Code */ int main() { vector<int> nums = {1, 1, 2}; vector<vector<int>> res = permutationsII(nums); cout << "入力配列 nums = "; printVector(nums); cout << "すべての順列 res = "; printVectorMatrix(res); return 0; }