冪集。編寫一種方法，返回某集合的所有子集。集合中不包含重復的元素。

說明：解集不能包含重復的子集。

示例

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

分析

從題意可以看出是使用回溯思想，由于要求集合中不包含重復的元素，所以可以先把輸入集合中重復的元素去掉并且排序，再進行回溯操作，回溯過程中確保始終向后遍歷就可以避免出現重復元素。

代碼

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        auto it = std::unique(nums.begin(), nums.end());
        nums.resize(std::distance(nums.begin(), it));
        vector<int> path;
        dfs(nums, 0, path);
        return ret;
    }

    vector<vector<int>> ret;
    void dfs(vector<int>& nums, int index, vector<int>& path) {
        ret.push_back(path);
        if (index == nums.size()) {
            return;
        }
        for (int i = index, size = nums.size(); i < size; ++i) {
            path.push_back(nums.at(i));
            dfs(nums, i+1, path);
            path.pop_back();
        }
    }
};

  代碼精進之路，我們一起成長！