Today I Learned

오늘은 leetcode medium 자바 코테 공부!

Permutations

https://leetcode.com/problems/permutations/

문제

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

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

풀이과정

• 백트래킹을 이용해 문제를 해결했다.

1. 2차원 list를 초기화하고, backtrack 메서드로 파라미터를 넣어 result를 반환 받는다.

2. backtrack 메서드에 순열을 저장할 2차원 리스트, 현재까지 생성된 순열을 저장하는 임시 arraylist, 순열을 생성할 원본 nums배열을 파라미터로 받는다.

3. tempList의 크기가 nums 배열의 길이와 같다면, 즉 현재 tempList가 하나의 순열을 완성했다면, 이 순열을 result 리스트에 추가한다.

4. nums를 순회하면서 tempList에 이미 nums[i]가 존재한다면 이번 루프를 건너뛴다. 즉, 중복된 요소를 허용하지 않는다.

5. tempList에 nums[i]를 추가합니다. 이는 새로운 순열의 요소를 하나 추가하는 것을 의미한다. 재귀적으로 backtrack 메서드를 호출하여 순열을 생성한다. tempList에서 마지막 요소를 제거하여 이전 상태로 되돌린다.

6. 즉, backtrack 메소드는 재귀적으로 가능한 모든 순열을 생성한다. tempList에 현재 순열을 저장하고, 백트래킹을 사용하여 중복된 요소를 건너뛰고 새로운 순열을 생성한다.

Java 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums){
        if(tempList.size() == nums.length){
            result.add(new ArrayList<>(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){ 
                if(tempList.contains(nums[i])) continue; 
                tempList.add(nums[i]);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}