algo-aha

数组有重复元素，不论组合或排列都应去重

不管是求组合还是排列，数组有重复元素时，要确保相同元素只选第一个。

• 可以排序数组，再看相邻元素，if (i > idx && nums[i] == nums[i-1]) continue;
• 如果不能排序，使用unordered_set<int> seen;

求所有可能组合：元素选一次还是多次？

• search(idx)从idx开始遍历
• 元素只选一次，递归时i+1；元素可选多次，递归时还是i。

/* 模板 */
void search(..., int idx, vector<int> &comb, vector<vector<int>> &ans) {
    // 前面是终止条件，对应子问题[idx,...]；
    if (idx == nums.size()) {
        ans.push_back(comb);
        return;
    }

    // 有重复元素，相同元素只选第一个；数组已排序
    for (int i = idx; i < nums.size(); i++) {
        if (i > idx && nums[i] == nums[i-1]) continue;

        comb.push_back(nums[i]);
        search(...); // 元素只选一次，递归时i+1；元素可选多次，递归时还是i
        comb.pop_back();
    }
}

    // 有重复元素，相同元素只选第一个；数组不能排序
    unordered_set<int> seen;
    for (int i = idx; i < nums.size(); i++) {
        if (seen.count(nums[i])) continue;
        seen.insert(nums[i]);
        ...
    }

题目：

• https://leetcode.com/problems/combination-sum 元素可选多次
• https://leetcode.com/problems/combination-sum-ii 元素只选一次、元素有重复
• https://leetcode.com/problems/combination-sum-iii 元素只选一次
• https://leetcode.com/problems/combinations/ 元素只选一次

特别地，要输出全组合，元素只选一次，有两种写法

// 记这种写法，只需改成前面不终止
void search(const vector<int> &nums, int idx, vector<int> &subset, vector<vector<int>> &ans) {
    // 前面不终止，对应子问题[...,idx)
    ans.push_back(subset);

    for (int i = idx; i < nums.size(); i++) {
        subset.push_back(nums[i]);
        search(nums, i + 1, subset, ans);
        subset.pop_back();
    }
}

// 这种写法不用记，考虑位置idx的各种可能
void subsets(const vector<int> &nums, int idx, vector<int> &subset, vector<vector<int>> &ans) {
    if (idx == nums.size()) {
        ans.push_back(subset);
        return;
    }

    // 不选
    subsets(nums, idx + 1, subset, ans);
    // 选
    subset.push_back(nums[idx]);
    subsets(nums, idx + 1, subset, ans);
    subset.pop_back();
}

• https://leetcode.com/problems/subsets/ 元素只选一次。这题也可对应[0, 2^n)间的二进制遍历，二进制中1选0不选
• https://leetcode.com/problems/subsets-ii/ 元素只选一次、元素有重复
• https://leetcode.com/problems/increasing-subsequences 元素只选一次、元素有重复

vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> seq;
    search(nums, 0, seq, ans);
    return ans;
}

void search(vector<int>& nums, int idx, vector<int> &seq, vector<vector<int>> &ans) {
    if (seq.size() >= 2) ans.push_back(seq);

    unordered_set<int> selected;
    for (int i = idx; i < nums.size(); i++) {
        if (selected.count(nums[i])) continue; // 确保相同元素只选第一个
        selected.insert(nums[i]);

        if (!seq.empty() && nums[i] < seq.back()) continue; // 确保递增
        seq.push_back(nums[i]);
        search(nums, i + 1, seq, ans);
        seq.pop_back();
    }
}

求所有可能排列：元素只选一次

• 元素只选一次，search()从idx开始遍历，考虑位置idx的各种可能（nums[idx]和nums[i>=idx]交换）、递归时idx+1；
• 元素可选多次，search()都从0开始遍历、不用idx参数

题目：

• https://leetcode.com/problems/permutations/ 元素只选一次
• https://leetcode.com/problems/permutations-ii 元素只选一次、元素有重复
• https://leetcode.com/problems/letter-case-permutation/ 元素只选一次

void search(vector<int> &nums, int idx, vector<vector<int>> &ans) {
    const int N = nums.size();
    if (idx == N) {
        ans.push_back(nums);
        return;
    }

    unordered_set<int> seen; // 排列去重，略过相同元素
    for (int i = idx; i < N; i++) {
        if (seen.count(nums[i])) continue;
        seen.insert(nums[i]);

        swap(nums[idx], nums[i]);
        search(nums, idx + 1, ans); // 这里是idx相关
        swap(nums[idx], nums[i]);
    }
}

或者，使用组合的写法，多用一个visited[]数组

void search(vector<int> &nums, vector<bool> &visited, 
            vector<int> &seq, vector<vector<int>> &ans) {
    const int N = nums.size();
    if (seq.size() == N) {
        ans.push_back(seq);
        return;
    }

    unordered_set<int> seen; // 排列去重，略过相同元素
    for (int i = 0; i < N; i++) {
        if (visited[i] || seen.count(nums[i])) continue;
        visited[i] = true;
        seen.insert(nums[i]);

        seq.push_back(nums[i]);
        search(nums, visited, seq, ans);
        seq.pop_back();
        visited[i] = false;
    }
}

联系：生成下一排列