매일 한 문제씩 Leet Code [33일차]

1388 단어
T46. Permutations【Medium】

제목


서로 다른 숫자의 집합을 제시하고 가능한 모든 배열 조합을 되돌려줍니다.
예를 들어, [1,2,3]에는 다음과 같은 배열 조합이 있습니다.
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

생각


이 문제는 귀착에 써야 한다는 것이 뚜렷하다. 귀착만 할 줄 알면 사고방식은 정상적인 아이들이 알 수 있는 사고방식이다.
 (1 2 3)
= 1 +  (2 3)∪ 2 +  (1 3)∪ 3 +  (1 2)
 (2 3)
= 2 +  (3)∪ 3 +  (2)
= 23 ∪ 32 

 

그리고 코드를 보시면 돼요.

코드


코드는 Top Solution에서 가져옵니다.
 public class Solution {
     public List> permute(int[] nums) {
         // 
        List> list = new ArrayList>();
         // 
        backtrack(list, new ArrayList(), nums);
        return list;
    }

    // : 
     public void backtrack(List> list, List tempList, int[] nums){
        if(tempList.size() == nums.length){
            //  ArrayList  
            list.add(new ArrayList(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){
                // , 
                if(tempList.contains(nums[i])) continue;
                // , 
                tempList.add(nums[i]);
                backtrack(list, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

좋은 웹페이지 즐겨찾기