# Two BackTracking Solutions. Which one is better?

• First. Insert new item to different position:

``````public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
List<List<Integer>> cur = new ArrayList<>();
for (List<Integer> l : res) {
int size = l.size();
for (int j = 0; j <= size; j++) {
l.remove(j);
}
}
res = cur;
}
return res;
}
}
``````

Second, use a flag table:

``````public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
search(res, list, visited, nums);
return res;
}

private void search(List<List<Integer>> res, List<Integer> list, boolean[] visited, int[] nums) {
if (list.size() == nums.length) {
return;
}
for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
visited[i] = true;
search(res, list, visited, nums);
visited[i] = false;
list.remove(list.size() - 1);
}
}
}
}
``````

I think the time complexity for both methods should be O(n!).
The second one seems more space efficient to me. Let me know if I'm wrong.
Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.