## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Permutations challenge – Iterative solution

Sharing is caring!

Problem statement
Given a list, `nums`, of distinct numbers, return all possible permutations.

Sample input

```[1,2,3]
```

Sample output

```[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
```

Solution
In another post we showed how this problem can be solved using a recursive technique by swapping. We stumbled upon a nice iterative solution that we thought might be worth sharing.

The idea is to start at an empty list of list `ans = [[]]`. We then iteratively are going to expand our `ans` list. We are going to do this by iterating over every number `n` in `nums` and insert it at every possible position in every list that is currently in `ans`.

Let `nums = [1,2,3]`. And let `ans = [[]]`. The first number is `1` and the first list in `ans` is `[]`. We then make a copy of `[]` and add `1` at every position in `[]` which results in ``. We add the newly created list to our new answer list and replace `ans` with that and repeat. The next number is `2`. We then iterate over `ans` and add `2` at every possible position in every list we iterate over in `ans`. The only list in `ans` is ``. So we make a copy and add `2` at position `0` and then make another copy and add `2` at position `1`. We add the resulting lists to our new answer list and replace `ans` with that list, resulting in `ans = [[2,1], [1,2]]`. The next number in `nums` is `3`. Again, we then iterate over `ans` (`[[2,1], [1,2]]`) and add `3` at every possible position in every list in `ans`. So for list `[2,1]` in `ans` we get `[3,2,1], [2,3,1], [2,1,3]` and for `[1,2]` we get `[3,1,2], [1,3,2], [1,2,3]` which results in our new and final `ans`.

Full code

```class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = [[]]
for n in nums:
new_ans = []
for perm in ans:
for i in range(0, len(perm) + 1):
new_ans.append(perm[:i] + [n] + perm[i:])
ans = new_ans

return ans

def main():
solution = Solution()
print(solution.permute([1, 2, 3]))

if __name__ == "__main__":
main()
```