Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.3 kB
3
Indexable
Never
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

void dfs(vector<int>& nums, vector<bool>& visited, vector<int>& path, vector<vector<int>>& res, int k) {
    if(path.size() == k) {
        res.push_back(path);
        return;
    }
    for(int i = 0; i < nums.size(); i++) {
        if(visited[i]) {
            continue;
        }
        if(i > 0 && nums[i] == nums[i-1] && !visited[i-1]) {
            continue;
        }
        path.push_back(nums[i]);
        visited[i] = true;
        dfs(nums, visited, path, res, k);
        path.pop_back();
        visited[i] = false;
    }
}

vector<vector<int>> permutation(vector<int>& nums, int k) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> visited(n);
    dfs(nums, visited, path, res, k);
    return res;
}

void printVector(vector<vector<int>>& res) {
    for(auto& vec : res) {
        cout << '[';
        for(auto& num : vec) {
            cout << num << ',';
        }
        cout << ']' << endl;
    }
}



int main()
{
    vector<int> nums = {1, 2, 3, 3};
    int k = 2;
    auto res = permutation(nums, k);
    cout << res.size() << endl;
    printVector(res);
    return 0;
}