Looking for good programming challenges?

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

Permutations challenge

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
We are using a technique called permutations by swapping.

Full code

class Solution(object):
    def swap(self, nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp

    def solve(self, nums, i, result):
        if i == len(nums)-1:
            result.append(list(nums))
            return

        for j in range(i, len(nums)):
            self.swap(nums, i, j)
            self.solve(nums, i+1, result)
            self.swap(nums, i, j)

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        self.solve(nums, 0, ans)
        return ans

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


if __name__ == "__main__": main()