C/C++每日一练(20230226)

目录

 

17. 电话号码的字母组合

37. 解数独

51. N 皇后

52. N皇后 II

89. 格雷编码

90. 子集 II

---

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<string> result;vector<string> letterCombinations(string digits){string temp;if (digits.length() == 0)return result;getAns(digits, 0, temp, result);return result;}void getAns(string digits, int start, string temp, vector<string> &result){if (temp.size() == digits.length())result.push_back(temp);else{vector<char> let = getLet(digits[start]);for (int i = 0; i < let.size(); i++){temp.append(1, let[i]);getAns(digits, start + 1, temp, result);temp.pop_back();}}}vector<char> getLet(char i){vector<char> let;if (i == '2'){let.push_back('a');let.push_back('b');let.push_back('c');}else if (i == '3'){let.push_back('d');let.push_back('e');let.push_back('f');}else if (i == '4'){let.push_back('g');let.push_back('h');let.push_back('i');}else if (i == '5'){let.push_back('j');let.push_back('k');let.push_back('l');}else if (i == '6'){let.push_back('m');let.push_back('n');let.push_back('o');}else if (i == '7'){let.push_back('p');let.push_back('q');let.push_back('r');let.push_back('s');}else if (i == '8'){let.push_back('t');let.push_back('u');let.push_back('v');}else if (i == '9'){let.push_back('w');let.push_back('x');let.push_back('y');let.push_back('z');}return let;}
};int main()
{Solution s1;string digits = "23";for (auto comb : s1.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s2;digits = "";for (auto comb : s2.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s3;digits = "2";for (auto comb : s3.letterCombinations(digits))cout << comb << " ";return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:unordered_map<char, string> map = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};vector<string> res;void backtrack(string &s, int index, string cur){if (index == s.size()){res.push_back(cur);return;}for (int i = 0; i < map[s[index]].size(); ++i)backtrack(s, index + 1, cur + map[s[index]][i]);}vector<string> letterCombinations(string digits){if (digits.size() == 0)return res;string cur;backtrack(digits, 0, cur);return res;}
};int main()
{Solution s1;string digits = "23";for (auto comb : s1.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s2;digits = "";for (auto comb : s2.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s3;digits = "2";for (auto comb : s3.letterCombinations(digits))cout << comb << " ";return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<string> letterCombinations(string digits){if (digits.size() == 0)return {};map<char, string> a;a.insert(map<char, string>::value_type('2', "abc"));a.insert(map<char, string>::value_type('3', "def"));a.insert(map<char, string>::value_type('4', "ghi"));a.insert(map<char, string>::value_type('5', "jkl"));a.insert(map<char, string>::value_type('6', "mno"));a.insert(map<char, string>::value_type('7', "pqrs"));a.insert(map<char, string>::value_type('8', "tuv"));a.insert(map<char, string>::value_type('9', "wxyz"));int count = 1;for (int i = 0; i < digits.size(); i++){count *= a[digits[i]].size();}vector<string> res(count);count = 1;for (int i = 0; i < digits.size(); i++){int index = 0;vector<string> temp(res.begin(), res.begin() + count);for (int k = 0; k < count; k++){for (auto c : a[digits[i]]){res[index] = temp[k] + c;index++;}}count *= a[digits[i]].size();}return res;}
};int main()
{Solution s1;string digits = "23";for (auto comb : s1.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s2;digits = "";for (auto comb : s2.letterCombinations(digits))cout << comb << " ";cout <<endl;Solution s3;digits = "2";for (auto comb : s3.letterCombinations(digits))cout << comb << " ";return 0;
} 

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

输入：

board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

输出：

    [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

 提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:void solveSudoku(vector<vector<char>> &board){Dfs(board, 0);}private:bool flag = false;void Dfs(vector<vector<char>> &board, int n){if (n > 0 && n <= 81)if (!JudgeIsNoWant(board, n - 1))return;if (n >= 81){flag = true;return;}int x = n / 9;int y = n % 9;if (board[x][y] != '.')Dfs(board, n + 1);else{for (int i = 1; i < 10; i++){board[x][y] = i + 48;Dfs(board, n + 1);if (flag == true)return;board[x][y] = '.';}}}bool JudgeIsNoWant(vector<vector<char>> &board, int n){int x = n / 9;int y = n % 9;for (size_t i = 0; i < 9; i++){if (board[x][i] == board[x][y] && i != y)return false;if (board[i][y] == board[x][y] && i != x)return false;}for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)if (board[i][j] == board[x][y] && (i != x || j != y))return false;return true;}
};int main()
{Solution s;vector<vector<char>>board = {{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout << row << " ";cout <<endl;}return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:void solveSudoku(vector<vector<char>> &board){int size = board.size();vector<vector<bool>> rows(size, vector<bool>(10));vector<vector<bool>> cols(size, vector<bool>(10));vector<vector<bool>> boxes(size, vector<bool>(10));for (int i = 0; i < size; i++){for (int j = 0; j < size; j++){if (board[i][j] != '.'){int num = board[i][j] - '0';int idx = i / 3 * 3 + j / 3;rows[i][num] = true;cols[j][num] = true;boxes[idx][num] = true;}}}dfs(board, 0, rows, cols, boxes);}
private:bool valid(int num, int row, int col, int idx, vector<vector<bool>> &rows,vector<vector<bool>> &cols, vector<vector<bool>> &boxes){return !rows[row][num] && !cols[col][num] && !boxes[idx][num];}bool dfs(vector<vector<char>> &board, int size, vector<vector<bool>> &rows,vector<vector<bool>> &cols, vector<vector<bool>> &boxes){if (size == 9 * 9){return true;}else{bool ok = false;int row = size / 9;int col = size % 9;int idx = row / 3 * 3 + col / 3;if (board[row][col] == '.'){for (int i = 1; i <= 9; i++){if (valid(i, row, col, idx, rows, cols, boxes)){board[row][col] = i + '0';rows[row][i] = true;cols[col][i] = true;boxes[idx][i] = true;ok = dfs(board, size + 1, rows, cols, boxes);if (!ok){rows[row][i] = false;cols[col][i] = false;boxes[idx][i] = false;board[row][col] = '.';}}}}else{ok = dfs(board, size + 1, rows, cols, boxes);}return ok;}}
};int main()
{Solution s;vector<vector<char>>board = {{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout << row << " ";cout <<endl;}return 0;
} 

以下代码错？不显示结果，输出起始board

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:int row[9][9], col[9][9], block[9][9];void solveSudoku(vector<vector<char>> &board){for (int i = 0; i < 9; ++i){for (int j = 0; j < 9; ++j){if (board[i][j] == '.')continue;int num = board[i][j] - '1';row[i][num] = col[j][num] = block[i / 3 * 3 + j / 3][num] = 1;}}dfs(board, 0, 0);}bool dfs(vector<vector<char>> &board, int r, int c){if (r > 8)return true;if (board[r][c] == '.'){for (int i = 0; i < 9; ++i){if (row[r][i] || col[c][i] || block[r / 3 * 3 + c / 3][i])continue;board[r][c] = i + 1 + '0';row[r][i] = col[c][i] = block[r / 3 * 3 + c / 3][i] = 1;if (dfs(board, r + (c + 1) / 9, (c + 1) % 9))return true;board[r][c] = '.';row[r][i] = col[c][i] = block[r / 3 * 3 + c / 3][i] = 0;}}elsereturn dfs(board, r + (c + 1) / 9, (c + 1) % 9);return false;}
};int main()
{Solution s;vector<vector<char>>board = {{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout << row << " ";cout <<endl;}return 0;
} 

51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<vector<string>> solveNQueens(int n){vector<vector<string>> res;vector<int> stack(n);vector<string> solution(n, string(n, '.'));dfs(n, 0, stack, solution, res);return res;}private:void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res){if (row == n){res.push_back(solution);}else{for (int i = 0; i < n; i++){if (row == 0 || !conflict(stack, row, i)){solution[row][i] = 'Q';stack[row] = i;dfs(n, row + 1, stack, solution, res);solution[row][i] = '.';}}}}bool conflict(vector<int> &stack, int row, int col){for (int i = 0; i < row; i++){if (col == stack[i] || abs(row - i) == abs(col - stack[i])){return true;}}return false;}
};int main()
{Solution s;int i = 0;for (auto res : s.solveNQueens(4)){cout << ++i << endl;for (auto item : res)cout << item << " ";cout << endl;}cout << endl;return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<vector<string>> res;vector<vector<string>> solveNQueens(int n){vector<string> board(n, string(n, '.'));backtrack(board, 0);return res;}void backtrack(vector<string> &board, int row){if (row == board.size()){res.push_back(board);return;}int n = board[row].size();for (int col = 0; col < n; col++){if (!isValid(board, row, col)){continue;}board[row][col] = 'Q';backtrack(board, row + 1);board[row][col] = '.';}}bool isValid(vector<string> &board, int row, int col){int n = board.size();for (int i = 0; i < row; i++){if (board[i][col] == 'Q'){return false;}}for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){if (board[i][j] == 'Q'){return false;}}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if (board[i][j] == 'Q'){return false;}}return true;}
};int main()
{Solution s;int i = 0;for (auto res : s.solveNQueens(4)){cout << ++i << endl;for (auto item : res)cout << item << " ";cout << endl;}cout << endl;return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:bool isValue(vector<int> &pos, int row, int col){for (int i = 0; i < row; ++i){if (col == pos[i] || abs(row - i) == abs(col - pos[i]))return false;}return true;}void solveNQueensDFS(vector<int> &pos, int row, vector<vector<string>> &ans){int n = pos.size();if (row == n){vector<string> tmp(n, string(n, '.'));for (int i = 0; i < n; ++i)tmp[i][pos[i]] = 'Q';ans.push_back(tmp);}else{for (int col = 0; col < n; ++col){if (isValue(pos, row, col)){pos[row] = col;solveNQueensDFS(pos, row + 1, ans);pos[row] = -1;}}}}vector<vector<string>> solveNQueens(int n){vector<int> pos(n, -1);vector<vector<string>> ans;solveNQueensDFS(pos, 0, ans);return ans;}
};int main()
{Solution s;int i = 0;for (auto res : s.solveNQueens(4)){cout << ++i << endl;for (auto item : res)cout << item << " ";cout << endl;}cout << endl;return 0;
} 

52. N皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:int totalNQueens(int n){vector<int> stack(n);return dfs(n, 0, stack);}private:int dfs(int n, int row, vector<int> &stack){int count = 0;if (row == n){return count + 1;}else{for (int i = 0; i < n; i++){if (row == 0 || !conflict(stack, row, i)){stack[row] = i;count += dfs(n, row + 1, stack);}}return count;}}bool conflict(vector<int> &stack, int row, int col){for (int i = 0; i < row; i++){if (col == stack[i] || abs(row - i) == abs(col - stack[i])){return true;}}return false;}
};int main()
{Solution s;cout << s.totalNQueens(1) << endl;cout << s.totalNQueens(4) << endl;cout << s.totalNQueens(8) << endl;return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:bool isvalid(vector<string> &temp, int i, int j){ //判断棋盘是否有效//for (int k = 0; k<temp[i].size(); ++k){//判断行。不用判断行了，每行放一个之后就会递归到下一行了//	if (temp[i][k] == 'Q') return false;//}for (int k = 0; k < i; ++k){ //判断列if (temp[k][j] == 'Q')return false;}for (int p = i - 1, q = j - 1; p >= 0 && q >= 0; --p, --q){ //判断左上对角线if (temp[p][q] == 'Q')return false;}for (int p = i - 1, q = j + 1; p >= 0 && q < temp.size(); --p, ++q){ //判断右上对角线if (temp[p][q] == 'Q')return false;}return true;}int dfs(int &count, vector<string> &temp, int i, int n){if (i == n)return ++count;for (int j = 0; j < n; ++j){if (isvalid(temp, i, j)){temp[i][j] = 'Q'; //递归前修改dfs(count, temp, i + 1, n);}temp[i][j] = '.'; //递归后恢复}return count;}int totalNQueens(int n){int count = 0;string aa;for (int i = 0; i < n; ++i)aa += '.';vector<string> temp(n, aa);return dfs(count, temp, 0, n);}
};int main()
{Solution s;cout << s.totalNQueens(1) << endl;cout << s.totalNQueens(4) << endl;cout << s.totalNQueens(8) << endl;return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:void recurse(vector<string> solution, int pos, vector<vector<bool>> validPos, int &result){int n = solution[0].size();if (pos == n){result++;return;}for (int i = 0; i < n; i++){if (!validPos[pos][i])continue;vector<vector<bool>> newPos = validPos;for (int j = pos; j < n; j++){newPos[j][i] = false;if (i - j + pos >= 0)newPos[j][i - j + pos] = false;if (i + j - pos < n)newPos[j][i + j - pos] = false;}solution[pos][i] = 'Q';recurse(solution, pos + 1, newPos, result);solution[pos][i] = '.';}return;}int totalNQueens(int n){int result = 0;vector<string> solution(n, string(n, '.'));vector<vector<bool>> validPos = vector<vector<bool>>(n, vector<bool>(n, true));recurse(solution, 0, validPos, result);return result;}
};int main()
{Solution s;cout << s.totalNQueens(1) << endl;cout << s.totalNQueens(4) << endl;cout << s.totalNQueens(8) << endl;return 0;
} 

89. 格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。

格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]
解释:00 - 001 - 111 - 310 - 2对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1

示例 2:

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。给定编码总位数为 n 的格雷编码序列，其长度为 2^n。当 n = 0 时，长度为 2^0 = 1。因此，当 n = 0 时，其格雷编码序列为 [0]。

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<int> grayCode(int n){int size = 1 << n;vector<int> res;for (int i = 0; i < size; i++){int graycode = i ^ (i >> 1);res.push_back(graycode);}return res;}
};int main()
{Solution s;vector<int> res = s.grayCode(2);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));cout << endl;res = s.grayCode(0);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<int> grayCode(int n){vector<int> res;for (int i = 0; i < (int)pow(2, n); i++)res.push_back(i ^ (i >> 1));return res;}
};int main()
{Solution s;vector<int> res = s.grayCode(2);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));cout << endl;res = s.grayCode(0);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<int> grayCode(int n){vector<int> res;res.push_back(0);if (n == 0)return res;int head = 1;for (int i = 0; i < n; i++){for (int j = res.size() - 1; j >= 0; j--){res.push_back(head + res[j]);}head <<= 1;}return res;}
};int main()
{Solution s;vector<int> res = s.grayCode(2);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));cout << endl;res = s.grayCode(0);copy(res.begin(), res.end(), ostream_iterator<int>(cout," "));return 0;
} 

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<vector<int>> subsetsWithDup(vector<int> &nums){vector<vector<int>> result;vector<int> item;set<vector<int>> rset;result.push_back(item);sort(nums.begin(), nums.end());CreatSet(0, result, item, nums, rset);return result;}void CreatSet(int i, vector<vector<int>> &result,vector<int> &item, vector<int> &nums,set<vector<int>> &rset){if (i >= nums.size())return;item.push_back(nums[i]);if (rset.find(item) == rset.end()){rset.insert(item);result.push_back(item);}CreatSet(i + 1, result, item, nums, rset);item.pop_back();CreatSet(i + 1, result, item, nums, rset);}
};int main()
{Solution s;vector<int> nums = {1,2,2};vector<vector<int>> res = s.subsetsWithDup(nums);for (auto r:res){copy(r.begin(), r.end(), ostream_iterator<int>(cout, " "));cout << endl;}return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<vector<int>> subsetsWithDup(vector<int> &nums){sort(nums.begin(), nums.end());vector<vector<int>> res;vector<int> cur;for (int i = 0; i <= nums.size(); i++){dfs(res, cur, nums, 0, i);}return res;}void dfs(vector<vector<int>> &res, vector<int> &cur, vector<int> &nums, int begin, int n){if (cur.size() == n){res.push_back(cur);return;}for (int i = begin; i < nums.size(); i++){if (i > begin && nums[i] == nums[i - 1])continue;cur.push_back(nums[i]);dfs(res, cur, nums, i + 1, n);cur.pop_back();}return;}
};int main()
{Solution s;vector<int> nums = {1,2,2};vector<vector<int>> res = s.subsetsWithDup(nums);for (auto r:res){copy(r.begin(), r.end(), ostream_iterator<int>(cout, " "));cout << endl;}return 0;
} 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<vector<int>> ans;vector<int> cur;vector<int> v;void dfs(int depth){ans.push_back(cur);if (depth == v.size())return;for (int i = depth; i < v.size(); ++i){if (i > depth && v[i] == v[i - 1])continue;cur.push_back(v[i]);dfs(i + 1);cur.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int> &nums){sort(nums.begin(), nums.end());v = nums;dfs(0);return ans;}
};string VectorToString(vector<int> vec, string split=",")
{if (vec.size()==0) return "[]";string res = "[";for (auto n:vec)res += to_string(n) + split;return res.substr(0, res.length() - split.size()) + "]";
}int main()
{Solution s;vector<int> nums = {1,2,2};vector<vector<int>> res = s.subsetsWithDup(nums);for (auto r:res){cout << VectorToString(r) << " ";}return 0;
}