[LeetCode] 46. Permutations

Problem

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.

---

Solution

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        // 필요 파라미터 : 전체리스트, tmpList, 배열
        backtrack(list, new ArrayList<>(), nums);
        return list;
    }
    private void backtrack(List<List<Integer>> list, List<Integer> tmpList, int[] nums) {
        // 만들어진 tmpList를 list에 넣기 = 재귀함수가 멈추는 구간
        if (tmpList.size() == nums.length) {
            list.add(new ArrayList<>(tmpList));
        } else {
            // tmpList 만들기
            for (int i = 0; i < nums.length; i++) {
                // 중복요소 삽입 방지
                if (tmpList.contains(nums[i])) continue;
                tmpList.add(nums[i]);
                backtrack(list, tmpList, nums);
                // 호출된 곳으로 돌아가면서 tmpList속 요소를 하나씩 지움. -> 새로운 tmpList를 만들 수 있음.
                tmpList.remove(tmpList.size() - 1);
            }
        }
    } 
}

Explanation

• 모든 경우의 수를 구하는 BT(BackTracking)문제이다.
• 만들어야 하는 함수가 반환하는 값은 아래와 같이 큰 리스트 안에 작은 리스트가 들어 있는 모습이다. 고로 작은 리스트를 먼저 만들고 큰 리스트에 삽입하는 작업이 필요하다.
• 작은 리스트와 큰 리스트는 반복 작업으로 만들어야 하는데, 본 솔루션에서는 재귀함수를 사용해 만들어 보겠다.

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

• 작은 리스트를 만들기 위한 재귀함수를 선언한다. 값을 반환하는 게 아니라 재귀함수가 반복적으로 호출되면서 큰 리스트에 작은 리스트를 넣는 작업이 진행되므로 반환값은 없도록 하고, 인수로는 문제에서 주어진 배열과, 큰 리스트 속에 들어가는 작은 리스트를 의미하는 tmpList를 작성해준다.
• 재귀 함수의 구현부에서는 tmpList에 배열 nums의 요소를 삽입하도록 하고 배열 nums의 다음 요소를 삽입하기 위해서 다시 재귀함수를 호출한다.

  private void backtrack(List<Integer> tmpList, int[] nums)
    tmpList.add(nums[0]);
    backtrack(tmpList, nums);
  

• 위와 같이 재귀함수를 호출하면 같은 요소만 tmpList에 삽입되므로, 배열 nums의 다음요소를 삽입하기 위하여 for반복문을 작성하고 for반복문 내부에 if조건문을 작성하여, 중복되는 요소가 들어가지 못하도록 한다.

  private void backtrack(List<Integer> tmpList, int[] nums)
    for (int i = 0; i < nums.length; i++) {
        if (tmpList.contains(nums[i])) continue;
        tmpList.add(nums[i]);
        backtrack(tmpList, nums);
    }
  

• 재귀 함수가 반복적으로 호출 되면서 작은 리스트를 의미하는 tmpList의 크기가 배열 nums의 크기와 같아졌을 때, 큰 리스트에 삽입되어야 하므로, if조건문을 작성해 작은 리스트의 크기가 배열 nums의 크기와 같아졌을 때, 큰 리스트에 들어가도록 한다.
• 재귀 함수의 선언부에 큰 리스트를 의미하는 list를 작성해준다.
• 재귀 함수가 종료되면 호출된 곳으로 돌아가게 되는데, 돌아온 자리에서도 계속해서 for반복문이 진행되고 있으므로, 이를 이용하면 중복요소가 존재하지 않는 tmpList를 만들 수 있다. for반복문의 마지막에, tmpList에 마지막으로 추가되었던 요소를 제거해주면 for반복문이 진행되는 동안 중복되지 않는 tmpList를 만들 수 있다.

  private void backtrack(List<List<Integer>> list, List<Integer> tmpList, int[] nums) {
    // 만들어진 tmpList를 list에 넣기 = 재귀함수가 멈추는 구간
    if (tmpList.size() == nums.length) {
        list.add(new ArrayList<>(tmpList));
    } else {
        // tmpList 만들기
        for (int i = 0; i < nums.length; i++) {
            // 중복요소 삽입 방지
            if (tmpList.contains(nums[i])) continue;
            tmpList.add(nums[i]);
            backtrack(list, tmpList, nums);
            // 호출된 곳으로 돌아가면서 tmpList속 요소를 하나씩 지움. -> 새로운 tmpList를 만들 수 있음.
            tmpList.remove(tmpList.size() - 1);
        }
    }
  } 
  

• 문제의 함수 첫 부분에 반환에 필요한 큰 리스트를 의미하는 list를 선언하고, 재귀 함수를 호출하도록한다. 그리고 완성된 list를 반환한다.

  List<List<Integer>> list = new ArrayList<>();
  // 필요 파라미터 : 전체리스트, tmpList, 배열
  backtrack(list, new ArrayList<>(), nums);
  return list;