Permutations(Array,Backtracking)

Given an array nums of distinct integers, return all the possible 

permutations

. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

뭔가 기본적인 컨셉의 문제인데,

 

이게 또 한 번쯤은 집고 넘어가줘야 찝찝한게 없다. 애증의 순열! Permutation!

 

잘 모르겠다 이 친구는..

 

1. Python

크게 Backtrack을 이용하는 경우와 Recursive를 이용하는 경우로 나뉜다.

 

# Back track O(N!)
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        def backtrack(start):
            if start == len(nums):
                res.append(nums[:]) # 이는 res.append(nums)가 nums의 참조(reference)저장하면 nums가 바뀜. 그러니 새로운 객체 저장 필요 nums[:]
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]

        res = []
        backtrack(0)
        return res
        
 # Recursive # O(N * N!)
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1 :
            return [nums[:]]
        
        ans = []

        for _ in range(len(nums)):
            n = nums.pop(0)
            perms = self.permute(nums)

            for p in perms:
                p.append(n)
            ans += perms
            nums.append(n)
        return ans

 

2. C

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize, int* temp) {
    if (start == numsSize) {
        result[*returnSize] = (int*)malloc(numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {
            result[*returnSize][i] = nums[i];
        }
        (*returnSize)++;
        return;
    }

    for (int i = start; i < numsSize; i++) {
        swap(&nums[start], &nums[i]);
        backtrack(nums, numsSize, start + 1, result, returnSize, temp);
        swap(&nums[start], &nums[i]);  // Backtrack
    }
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int totalPermutations = 1;
    for (int i = 2; i <= numsSize; i++) {
        totalPermutations *= i;
    }

    int** result = (int**)malloc(totalPermutations * sizeof(int*));
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(totalPermutations * sizeof(int));

    backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes);

    for (int i = 0; i < totalPermutations; i++) {
        (*returnColumnSizes)[i] = numsSize; 
    }

    return result;
}
void printPermutations(int** permutations, int returnSize, int* returnColumnSizes) {
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", permutations[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(", ");
        }
        printf("]\n");
        free(permutations[i]);
    }
    free(permutations);
    free(returnColumnSizes);
}