[Leetcode,c++] Subsets II

문제

Subsets II - LeetCode

 

코드

class Solution {
public:
    map<vector<int>,int>visited;
    vector<vector<int>>ans;

    void dfs(int num, vector<int>&nums,vector<int>current){

        sort(current.begin(),current.end());
        if(!visited[current]){
            ans.push_back(current);
            visited[current]=1;
        }

        if(num>nums.size()) return;

        for(int i=num; i<nums.size(); i++){
            vector<int>temp=current;
            temp.push_back(nums[i]);
            dfs(i+1,nums,temp);
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            dfs(i,nums,{});
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

 

풀이

backtraking 문제입니다.

inp: [4,4,4,1,4]
out: [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]

위 처럼 정렬 된 채로 출력해야 하기 때문에 정렬을 해주는게 관건이며, 저는 map<vector<int>,int>visited 을 통해 방문 처리를 하여 중복처리를 제거했습니다.