13道medium+2道hard，看起来还好，其实题的难度一般，偏回溯的部分都还行。
休息了挺久，开始复健😋
(medium)200. 岛屿数量
一道很简单的图遍历，只需要一直遍历每个值为1的点的上下左右四个位置，为1的就记录其vis = 1；然后每遍历一个值为1且vis = 0的点就ans++即可(每遍历一次时其过程中vis值从0变为1的点代表其属于这块岛屿)。代码如下：
class Solution {
public:
void find(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tempx = x + xx[i];
int tempy = y + yy[i];
if(tempx >= 0 && tempy >= 0 && res[tempx][tempy] && !vis[tempx][tempy])
{
vis[tempx][tempy] = 1;
find(tempx, tempy);
}
}
return ;
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
ans = 0;
for(int i = 0; i < n; i++)
{
res.push_back({});
if(i == 0)
{
for(int j = 0; j < m + 2; j++)
res[0].push_back(0);
res.push_back({});
}
res[i + 1].push_back(0);
for(int j = 0; j < m; j++)
{
res[i + 1].push_back(grid[i][j] - '0');
}
res[i + 1].push_back(0);
}
res.push_back({});
for(int j = 0; j < m + 2; j++)
res[n + 1].push_back(0);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(res[i][j] && !vis[i][j])
{
ans++;
vis[i][j] = 1;
find(i, j);
}
}
}
return ans;
}
private:
int ans;
vector<vector<int>> res;
bool vis[301][301];
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
};(medium)130. 被围绕的区域
这道题我最开始思路和上道题一样，但苦于不知如何判断是否被X包围，看题解才知道其实可以从边界点开始搜，如果边界点的O能搜到该点且该点同样为O，则该点未被包围。代码如下：
class Solution {
public:
void find(int x, int y, vector<vector<char>>& board)
{
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
return ;
board[x][y] = 'N';
for(int i = 0; i < 4; i++)
{
int tempx = x + xx[i];
int tempy = y + yy[i];
find(tempx, tempy, board);
}
}
void solve(vector<vector<char>>& board) {
m = board.size();
n = board[0].size();
//从每行的首列和最后一列开始搜
for(int i = 0 ; i < m; i++)
{
find(i, 0, board);
find(i, n - 1, board);
}
//从每列的首行和末行开始搜
for(int i = 0; i < n; i++)
{
find(0, i, board);
find(m - 1, i, board);
}
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(board[i][j] == 'N')
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}
return ;
}
private:
int m, n;
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
};(medium)133. 克隆图
真的是牛魔题，就tm是一个拷贝完全相同的图，非得要说的跟尼玛谷歌翻译的中文一样😓。我是用的深搜，每次更新node时先更新完其邻居，再更新当前节点。代码如下：
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == NULL)
return node;
// 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
if (vis[node->val])
return vis[node->val];
// 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
Node* newNode = new Node(node->val);
vis[node->val] = newNode;
// 遍历该节点的邻居并更新克隆节点的邻居列表
for (auto& neighbor: node->neighbors)
newNode->neighbors.push_back(cloneGraph(neighbor));
return newNode;
}
private:
unordered_map<int,Node*> vis;
};(medium)399. 除法求值
本质也是一张无向图，A-B这条边的值为val，表示A/B=val,B/A=1/val。根据equations和values进行建图，然后每次询问时看询问的两个节点能否到达，不能则值为-1.0，能则值为其过程中每条边的值乘积。代码如下：
class Node {
public:
vector<double> val;
vector<Node*> neighbors;
Node() {
val = vector<double>();
neighbors = vector<Node*>();
}
};
class Solution {
public:
double find(Node* start, Node* end)
{
if(start == NULL || end == NULL)
return 0.0;
if(start == end)
return 1.0;
for(int i = 0; i < start->neighbors.size(); i++)
{
if(!vis[start->neighbors[i]])
{
vis[start->neighbors[i]] = 1;
double tmp = find(start->neighbors[i], end);
vis[start->neighbors[i]] = 0;
if(tmp != 0.0)
return tmp * start->val[i];
}
}
return 0.0;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<double> ans;
for(int i = 0; i < equations.size(); i++)
{
string tmp = equations[i][0];
string tmp2 = equations[i][1];
if(!a[tmp])
{
a[tmp] = new Node();
}
if(!a[tmp2])
{
a[tmp2] = new Node();
}
a[tmp]->neighbors.push_back(a[tmp2]);
a[tmp]->val.push_back(values[i]);
a[tmp2]->neighbors.push_back(a[tmp]);
a[tmp2]->val.push_back(1.0/values[i]);
}
for(int i = 0; i < queries.size(); i++)
{
string tmp = queries[i][0];
string tmp2 = queries[i][1];
double ans_cnt = find(a[tmp], a[tmp2]);
if(ans_cnt == 0.0)
ans_cnt = -1.0;
ans.push_back(ans_cnt);
}
return ans;
}
private:
unordered_map<string,Node*> a;
unordered_map<Node*,bool> vis;
};(medium)207. 课程表
写完才想起来这是拓扑排序的写法。本质其实就是给a b两个点，b->a，判断这个图是否存在回环，有回环就寄。那么我们就以每个之前没有跑到的点(因为如果该点之前跑过，那以该点为起点的情况也已经跑过)作为起点。vis[i]用于判断i的状态，为0表示还未访问过，为1表示正在状态中，为2表示已经跑完了。显而易见，当碰到一个vis[i]=1的点时，说明回环了；而碰到vis[i]=0的时候则继续跑i；vis[i]=2表示已经跑过了，就不用管它。具体实现代码如下：
struct node
{
vector<int> pre;
node() {
pre = vector<int>();
}
};
class Solution {
public:
void find(int a)
{
//a现在正在搜索
vis[a] = 1;
if(add[a])
{
for(int i = 0; i < add[a]->pre.size(); i++)
{
int tmp = add[a]->pre[i];
if(!vis[tmp])
{
find(tmp);
if(!flag)
return ;
}
else if(vis[tmp] == 1)//形成了环
{
flag = 0;
return ;
}
}
}
//以a为边搜索完毕
vis[a] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
add.resize(numCourses, NULL);
vis.resize(numCourses, 0);
flag = 1;
for(int i = 0; i < prerequisites.size(); i++)
{
int a = prerequisites[i][0];
int b = prerequisites[i][1];
if(add[b] == NULL)
{
add[b] = new node();
}
if(add[a] == NULL)
{
add[a] = new node();
}
add[b]->pre.push_back(a);
}
for(int i = 0; i < numCourses && flag; i++)
{
if(!vis[i])
find(i);
}
return flag;
}
private:
vector<node*> add;
vector<int> vis;
bool flag;
};(medium)210. 课程表 II
和上题基本一模一样，唯一区别就是每次跑完当前节点之后要把当前节点放入栈ans末尾(因为当vis[i]=2时表示其pre节点都已访问完正常入栈，所以i此时正常进入末尾)。代码如下：
struct node
{
vector<int> pre;
node() {
pre = vector<int>();
}
};
class Solution {
public:
void find(int a)
{
//a现在正在搜索
vis[a] = 1;
if(add[a])
{
for(int i = 0; i < add[a]->pre.size(); i++)
{
int tmp = add[a]->pre[i];
if(!vis[tmp])
{
find(tmp);
if(!flag)
return ;
}
else if(vis[tmp] == 1)//形成了环
{
flag = 0;
return ;
}
}
}
//以a为边搜索完毕
ans.push_back(a);
vis[a] = 2;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
add.resize(numCourses, NULL);
vis.resize(numCourses, 0);
flag = 1;
for(int i = 0; i < prerequisites.size(); i++)
{
int a = prerequisites[i][0];
int b = prerequisites[i][1];
if(add[b] == NULL)
{
add[b] = new node();
}
if(add[a] == NULL)
{
add[a] = new node();
}
add[a]->pre.push_back(b);
}
for(int i = 0; i < numCourses && flag; i++)
{
if(!vis[i])
find(i);
}
if(flag)
return ans;
else
return {};
}
private:
vector<node*> add;
vector<int> vis;
vector<int> ans;
bool flag;
};(medium)909. 蛇梯棋
翻译真的是翻译了个牛魔酬宾，尼玛看题解我才明白题目啥意思😄。就是一道广搜版题(深搜我感觉应该也行，加个记忆化tmp[i]表示 从i到目标点的最小距离)，唯一卡了下的就是最后说的如果目标点为蛇/绳子的情况。当目标点为蛇/绳子，则把board[x[i]][y[i]]放入队列，否则就把i压入队列。每次结束一次队列就ans++。代码如下：
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
int target = n * n;
xx.resize(target + 1);
yy.resize(target + 1);
vis.resize(target + 1, 0);
int cnt = 1;
for(int i = n - 1; i >= 0; i--)
{
if((i - n + 1) & 1)
for(int j = n - 1; j >= 0; j--)
{
xx[cnt] = i;
yy[cnt] = j;
cnt++;
}
else
{
for(int j = 0; j < n; j++)
{
xx[cnt] = i;
yy[cnt] = j;
cnt++;
}
}
}
queue<int>q;
q.push(1);
int ans = 0;
while(!q.empty())
{
int l = q.size();
while(l--)
{
int now = q.front();
q.pop();
if(now == target)
return ans;
for(int i = 1; i <= 6 && now + i <= target; i++)
{
if(vis[now + i])
continue;
vis[now + i] = 1;
int x = xx[now + i];
int y = yy[now + i];
if(board[x][y] != -1)
{
if(now + i == target)
return ans + 1;
q.push(board[x][y]);
}
else
q.push(now + i);
}
}
//以每个点为起点的状态搜索完毕之后都++
ans++;
}
return -1;
}
private:
vector<int> xx;
vector<int> yy;
vector<bool> vis;
};(medium)433. 最小基因变化
同广搜版题，入列条件是和当前队头比较不同字符为1。代码如下：
class Solution {
public:
int getdiff(string a, string b)
{
int len = size(a);
int ans = 0;
for(int i = 0 ; i < len ; i++)
{
if(a[i] != b[i])
ans++;
}
return ans;
}
int minMutation(string startGene, string endGene, vector<string>& bank) {
int n = bank.size();
vis.resize(n , 0);
int target = -1;
int cnt = 0;
for(int i = 0 ; i < n ; i++)
{
if(endGene == bank[i])
{
target = i;
break;
}
}
if(target == -1)
return -1;
queue<string>q;
q.push(startGene);
while(!q.empty())
{
cnt++;
int l = q.size();
while(l--)
{
string tmp = q.front();
q.pop();
for(int j = 0 ; j < n ; j++)
{
if(!vis[j])
{
if(getdiff(tmp, bank[j]) == 1)
{
if(bank[j] == endGene)
return cnt;
vis[j] = 1;
q.push(bank[j]);
}
}
}
}
}
return -1;
}
private:
vector<int> vis;
};(hard)127. 单词接龙
最开始想的单向队列，速度巨慢，过倒是能过。代码如下：
class Solution {
public:
int getdiff(string a, string b)
{
int len = size(a);
int ans = 0;
for(int i = 0 ; i < len ; i++)
{
if(a[i] != b[i])
ans++;
}
return ans;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
bool flag = 0;
vis.resize(n , 0);
for(int i = 0 ; i < n ; i++)
{
if(wordList[i] == endWord)
{
flag = 1;
break;
}
}
if(!flag)
return 0;
queue<string>q;
q.push(beginWord);
int cnt = 1;
while(!q.empty())
{
cnt++;
int l = q.size();
while(l--)
{
string tmp = q.front();
q.pop();
for(int i = 0 ; i < n ; i++)
{
if(!vis[i] && getdiff(tmp, wordList[i]) == 1)
{
if(wordList[i] == endWord)
return cnt;
q.push(wordList[i]);
vis[i] = 1;
}
}
}
}
return 0;
}
private:
vector<int> vis;
};之后改成双向队列，速度上去了些，代码如下：
class Solution {
public:
int getdiff(string a, string b)
{
int len = size(a);
int ans = 0;
for(int i = 0 ; i < len ; i++)
{
if(a[i] != b[i])
ans++;
}
return ans;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
bool flag = 0;
vis.resize(n , 0);
vis2.resize(n , 0);
for(int i = 0 ; i < n ; i++)
{
if(wordList[i] == endWord)
{
//因为q是从endWord开始的，所以该位置的vis2默认为1，已经入栈过了
vis2[i] = 1;
flag = 1;
break;
}
}
if(!flag)
return 0;
if(getdiff(beginWord, endWord) == 1)
return 2;
queue<string>q;
queue<string>p;
q.push(beginWord);
p.push(endWord);
int cnt = 1;
while(!q.empty() && !p.empty())
{
int l = q.size();
int t = p.size();
cnt++;
if(l <= t)
{
while(l--)
{
string tmp = q.front();
q.pop();
for(int i = 0 ; i < n ; i++)
{
if(!vis[i])
{
if(getdiff(tmp,wordList[i]) == 1)
{
if(vis2[i])
return cnt;
q.push(wordList[i]);
vis[i] = 1;
}
}
}
}
}
else
{
while(t--)
{
string tmp = p.front();
p.pop();
for(int i = 0 ; i < n ; i++)
{
if(!vis2[i])
{
if(getdiff(tmp,wordList[i]) == 1)
{
if(vis[i])
return cnt;
p.push(wordList[i]);
vis2[i] = 1;
}
}
}
}
}
}
return 0;
}
private:
vector<bool> vis;
vector<bool> vis2;
};之后看题解，有人提示到说因为是全由26个小写字母构成，所以不需要每次循环n次看是否存在单词列表，只需要尝试改变每一位，看改变之后的是否存在于单词列表即可，相对上面解法而言快很多，但是空间占用是3倍。代码如下：
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
bool flag = 0;
int i = 0;
for(i = 0 ; i < n ; i++)
{
vis[wordList[i]] = 1;
vis2[wordList[i]] = 1;
if(wordList[i] == endWord)
{
flag = 1;
break;
}
}
for(i ; i < n ; i++)
{
vis[wordList[i]] = 1;
vis2[wordList[i]] = 1;
}
//vis和vis为1表示存在且未使用。
vis2[endWord] = 0;
if(!flag)
return 0;
queue<string>q;
queue<string>p;
q.push(beginWord);
p.push(endWord);
int cnt = 1;
while(!q.empty() && !p.empty())
{
int l = q.size();
int t = p.size();
cnt++;
if(l <= t)
{
while(l--)
{
string tmp = q.front();
q.pop();
int ed = tmp.length();
for(int i = 0 ; i < ed ; i++)
{
char k = tmp[i];
for(char ch = 'a' ; ch <= 'z' ; ch++)
{
if(k != ch)
{
tmp[i] = ch;
if(vis[tmp])
{
if(!vis2[tmp])
return cnt;
q.push(tmp);
vis[tmp] = 0;
}
tmp[i] = k;
}
}
}
}
}
else
{
while(t--)
{
string tmp = p.front();
p.pop();
int ed = tmp.length();
for(int i = 0 ; i < ed ; i++)
{
char k = tmp[i];
for(char ch = 'a' ; ch <= 'z' ; ch++)
{
if(k != ch)
{
tmp[i] = ch;
if(vis2[tmp])
{
if(!vis[tmp])
return cnt;
p.push(tmp);
vis2[tmp] = 0;
}
tmp[i] = k;
}
}
}
}
}
}
return 0;
}
private:
unordered_map<string,bool> vis;
unordered_map<string,bool> vis2;
};(medium)208. 实现 Trie (前缀树)
前缀树基本知识都记得住，所以很快就写出来了，基本原理就是若当前位置的nxt[i]非空，则指向当前位置的下一个'a'+i字母。代码如下：
struct node
{
bool end;
node* nxt[26];
node()
{
end = 0;
}
};
class Trie {
public:
Trie() {
end = 0;
memset(nxt, 0 ,sizeof(nxt));
}
void insert(string word) {
int n = word.size();
Trie* now = this;
for(int i = 0 ; i < n ; i++)
{
int num = word[i] - 'a';
if(now->nxt[num] == NULL)
{
now->nxt[num] = new Trie();
}
now = now->nxt[num];
}
now->end = 1;
return ;
}
bool search(string word) {
int n = word.size();
Trie* now = this;
for(int i = 0 ; i < n ; i++)
{
int num = word[i] - 'a';
if(now->nxt[num] == NULL)
{
return 0;
}
now = now->nxt[num];
}
if(now->end)
return 1;
return 0;
}
bool startsWith(string prefix) {
int n = prefix.size();
Trie* now = this;
for(int i = 0 ; i < n ; i++)
{
int num = prefix[i] - 'a';
if(now->nxt[num] == NULL)
{
return 0;
}
now = now->nxt[num];
}
return 1;
}
private:
bool end;
Trie* nxt[26];
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/(medium)211. 添加与搜索单词 - 数据结构设计
本质就是套用上道题的数据结构，只不过遇到.的时候把当前位置所有的nxt都得遍历。代码如下：
class WordDictionary {
public:
WordDictionary() {
end = 0;
memset(nxt , 0 , sizeof(nxt));
}
bool find(int pos , WordDictionary* now , string s , int s_length)
{
if(pos >= s_length)
return now->end;
if(s[pos] == '.')
{
for(int i = 0 ; i < 26 ; i++)
{
if(now->nxt[i] != NULL)
{
if(find(pos + 1 , now->nxt[i] , s , s_length))
return 1;
}
}
return 0;
}
int tmp = s[pos] - 'a';
if(now->nxt[tmp] == NULL)
return 0;
return find(pos + 1 , now->nxt[tmp] , s , s_length);
}
void addWord(string word) {
WordDictionary* now = this;
int n = word.length();
for(int i = 0 ; i < n ; i++)
{
int tmp = word[i] - 'a';
if(now->nxt[tmp] == NULL)
now->nxt[tmp] = new WordDictionary();
now = now->nxt[tmp];
}
now->end = 1;
return ;
}
bool search(string word) {
WordDictionary* now = this;
int n = word.length();
return find(0 , now , word , n);
}
private:
bool end;
WordDictionary* nxt[26];
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/(hard)212. 单词搜索 II
本质也是字典树，只不过不是把能组成的字符串加入到字典树中，而是把需要查询的字符串加入到字典树中，再去针对每个字符串能否倍正确组成。代码如下：
struct node
{
bool isok;
node* nxt[26];
};
class Solution {
public:
void NODE()
{
head = new node();
}
void add(string s)
{
node* now = head;
int n = s.length();
for(int i = 0 ; i < n ; i++)
{
int tmp = s[i] - 'a';
if(now->nxt[tmp] == NULL)
{
now->nxt[tmp] = new node();
}
now = now->nxt[tmp];
now->isok = 0;
}
return ;
}
void dfs(int x, int y, node* now)
{
if(x < 0 || y < 0 || x >= m || y >= n || vis[x][y])
return ;
int temp = tmp[x][y] - 'a';
if(now->nxt[temp] == NULL)
return ;
now->nxt[temp]->isok = 1;
vis[x][y] = 1;
for(int i = 0 ; i < 4 ; i++)
dfs(x + xx[i] , y + yy[i], now->nxt[temp]);
vis[x][y] = 0;
return ;
}
bool find(string s)
{
node* now = head;
int n = s.length();
for(int i = 0 ; i < n ; i++)
{
int tmp = s[i] - 'a';
if(!now->nxt[tmp]->isok)
return 0;
now = now->nxt[tmp];
}
return 1;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
NODE();
vector<string> ans;
int t = words.size();
for(int i = 0 ; i < t ; i++)
add(words[i]);
m = board.size();
n = board[0].size();
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < n ; j++)
tmp[i][j] = board[i][j];
}
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < n ; j++)
{
dfs(i , j , head);
}
}
for(int i = 0 ; i < t ; i++)
{
if(find(words[i]))
ans.push_back(words[i]);
}
return ans;
}
private:
int cnt;
node* head;
int xx[4] = {0 , 0 , 1 , -1};
int yy[4] = {-1 , 1 , 0 , 0};
bool vis[13][13];
int n , m;
char tmp[13][13];
};(medium)17. 电话号码的字母组合
一道很简单的映射题，花我时间最久的地方其实是把对应的表输进去()。代码如下：
class Solution {
public:
void dfs(int pos, string s)
{
if(pos >= n)
{
if(s != "")
ans.push_back(s);
return ;
}
for(int i = 0 ; i < 4 && phone[num[pos]][i] != '\0' ; i++)
{
dfs(pos + 1 , s + phone[num[pos]][i]);
}
}
vector<string> letterCombinations(string digits) {
n = digits.length();
for(int i = 0 ; i < n ; i++)
{
num.push_back(digits[i] - '0');
}
dfs(0 , {});
return ans;
}
private:
int n;
vector<int> num;
vector<string> ans;
char phone[10][4] = {
{'\0', '\0', '\0', '\0'}, // 0
{'\0', '\0', '\0', '\0'}, // 1
{'a', 'b', 'c', '\0'}, // 2
{'d', 'e', 'f', '\0'}, // 3
{'g', 'h', 'i', '\0'}, // 4
{'j', 'k', 'l', '\0'}, // 5
{'m', 'n', 'o', '\0'}, // 6
{'p', 'q', 'r', 's'}, // 7
{'t', 'u', 'v', '\0'}, // 8
{'w', 'x', 'y', 'z'} // 9
};
};(medium)77. 组合
也是一道基本的回溯题，byd返回答案而不是直接输出答案真恶心啊😓。代码如下：
class Solution {
public:
void dfs(int now , int num , vector<int> tmp)
{
if(num == k)
{
ans.push_back(tmp);
return ;
}
for(int i = now + 1 ; i <= n ; i++)
{
tmp.push_back(i);
dfs(i , num + 1 , tmp);
tmp.pop_back();
}
return ;
}
vector<vector<int>> combine(int n1, int k1) {
n = n1;
k = k1;
dfs(0 , 0 , {});
return ans;
}
private:
int n , k;
vector<vector<int>> ans;
};(medium)46. 全排列
也是经典回溯模板题了，再说一遍，返回结果而不是直接输出结果真的很恶心😄。代码如下：
class Solution {
public:
void dfs(int now , int num , vector<int> tmp)
{
if(num == n)
{
ans.push_back(tmp);
return ;
}
vis[now] = 1;
for(int i = 1 ; i <= n ; i++)
{
if(!vis[i])
{
tmp.push_back(k[i]);
dfs(i , num + 1 , tmp);
tmp.pop_back();
}
}
vis[now] = 0;
}
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
for(int i = 0 ; i < n ; i++)
k[i + 1] = nums[i];
dfs(0 , 0 , {});
return ans;
}
private:
int n;
int k[8];
bool vis[8];
vector<vector<int>> ans;
};