# My AC simple iterative java/python solution

• the basic idea is, to permute n numbers, we can add the nth number into the resulting `List<List<Integer>>` from the n-1 numbers, in every possible position.

For example, if the input num[] is {1,2,3}: First, add 1 into the initial `List<List<Integer>>` (let's call it "answer").

Then, 2 can be added in front or after 1. So we have to copy the List<Integer> in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {{2,1},{1,2}}. There are 2 lists in the current answer.

Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.

``````public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num.length ==0) return ans;
List<Integer> l0 = new ArrayList<Integer>();
for (int i = 1; i< num.length; ++i){
List<List<Integer>> new_ans = new ArrayList<List<Integer>>();
for (int j = 0; j<=i; ++j){
for (List<Integer> l : ans){
List<Integer> new_l = new ArrayList<Integer>(l);
}
}
ans = new_ans;
}
return ans;
}
``````

python version is more concise:

``````def permute(self, nums):
perms = [[]]
for n in nums:
new_perms = []
for perm in perms:
for i in xrange(len(perm)+1):
new_perms.append(perm[:i] + [n] + perm[i:])   ###insert n
perms = new_perms
return perms``````

• I used your idea of adding each next value to every possible position of current list, but have done it with recursion.

``````public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length == 0) return result;

backtrack(result, nums, new ArrayList<Integer>(), 0);

return result;
}

private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> currentList, int index) {
if (currentList.size() == nums.length) {
return;
}

int n = nums[index];
for (int i = 0; i <= currentList.size(); i++) {
List<Integer> copy = new ArrayList<Integer>(currentList);
backtrack(result, nums, copy, index + 1);
}

}
``````

I guess both solutions have the same complexity

• Very nice solution! you can simply a little bit by removing a couple of lines:

``````	public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num.length ==0)
return ans;
for (int i = 0; i< num.length; ++i){
List<List<Integer>> new_ans = new ArrayList<List<Integer>>();
for (int j = 0; j<=i; ++j){
for (List<Integer> l : ans){
List<Integer> new_l = new ArrayList<Integer>(l);
}
}
ans = new_ans;
}
return ans;
}``````

• A tiny improvement for Java solution, we don't really need the special case for the first element. Just `ans.add(l0);` add the empty list and let the loop starts from 0 `for (int i = 0; i< num.length; ++i){` :)

• Good idea! I was thinking we can optimize the solution by adding on to a single answer list instead of recreating a new list every time!

``````public class Solution {
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0) return result;
for(int i = 1; i < nums.length; i++) {
int curSize = result.size();
for(int j = 0; j < curSize; j++) {
for(int x = 0; x < result.get(j).size(); x++) {
}
}
}
return result;
}
}``````

• I used your idea, but have a slightly different starting point before getting into the loop. I think it's logically more clear and don't need to handle corner case when num is empty.

``````public List<List<Integer>> permute(int[] num) {

List<List<Integer>> rst = new ArrayList<List<Integer>>();

for (int i = 0; i < num.length; i++) {
List<List<Integer>> tmpRst = new ArrayList<List<Integer>>();
for (List<Integer> pm : rst) {
for (int j = 0; j < pm.size() + 1; j++) {
List<Integer> tmpPm = new ArrayList<Integer>(pm);
}
}

rst = new ArrayList<List<Integer>>(tmpRst);
}

return rst;
}``````

• Very well explained. Thanks a ton!

• liji94188 is right. We don't need the special case for empty array and the first element.

• Hi, Can someone please explain the time Complexity for the above solution? I believe it to be n^3 but I am not sure!

• C++ version:

class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> num;
num.push_back(nums[0]);
result.push_back(num);
for(int i=1;i<nums.size();i++){
vector<vector<int>> tmp;
for(int j=0;j<=i;j++){
for(auto it :result){
auto it2=it.begin();
it.insert(it2+j,nums[i]);
tmp.push_back(it);
}
}
result = tmp;
}
return result;
}
};

• @akshat5 The complexity is proportional to the size of the output (number of permutations). Just imagine that for the first position you have n possible candidates, then for the second position you have n-1 possible candidates (as the one is already taken in the first position), for the 3rd position you have n-2 candidates, etc. Therefore the complexity is O(n!). Also you can think in opposite way: in the beginning you have 1 element, next iteration you create 2 elements from it (add element in the beginning and at the end), so 12 operations, on the next step for each existing element you make 3 operations, so 12*3, etc.

• Here is C++ version Running time -16 ms

``````vector<vector<int>> permute(vector<int>& nums) {
vector<int> curr;
vector<vector<int> > ans;
if(nums.size()==0)
return ans;
curr.push_back(nums[0]); // insert first element
ans.push_back(curr); // insert the vector with first element
for(int i=1;i<nums.size();i++) // start from 2nd element of list
{
vector<vector<int> > new_ans;
for(int j=0;j<=i;j++) // insert nums[i] at 0->i position in result list
{
for(auto itr = ans.begin();itr!=ans.end();itr++) // get every list from ans to insert num[i]
{
vector<int> curr1(*itr); // copy the list into new vector
curr1.insert(curr1.begin()+j,nums[i]); // insert num[i] at pos j
new_ans.push_back(curr1); // insert new list into new ans
}
}
ans = new_ans; // copy ans
}
return ans;
}
``````

• @garik for time complexity I think we should also need to consider inserting into list and copying list so complexity should be greater than !n

• loop itself would be n^3, and copy would be n, insertion would be logn, Can I assume it would be n^4logn?

• @cbmbbz nice solution for using an iterative instead of recursive method

• nice solution

• @neer1304 Yes, greater than N!

• then do the same thing for position 3

typo here... should be position 2

• Would someone please do me a favor by analyzing the time and space complexity of the implementation? Thank you very much in advance!

• @cbmbbz
I'm confused about the space complexity...I will say space is O(N!)<- or total # of output intuitively, but in every fool-i loop, you create a new res, which will be (N-1), and the following for-j & for-list loop, you create new copy of every existing list in the ans....So will it be O(N-1) * O(N!)<- final result => O(N*N!) ?

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