46. Permutations (순열)

서로 다른 정수로 이루어진 배열 'nums'가 주어지면 가능한 모든 순열을 반환합니다. 당신은 어떤 순서로든 답을 반환할 수 있습니다.

 

예시 1:

입력: nums = [1,2,3]
출력: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

예시 2:

입력: nums = [0,1]
출력: [[0,1],[1,0]]

 

예시 3:

입력: nums = [1]
출력: [[1]]

 

조건:

• 1 <= nums.length <= 6
•  -10 <= nums[i] <= 10
• 'nums'의 모든 정수는 고유값입니다.

 

정답:

public class Solution 
{
    IList<IList<int>> result = new List<IList<int>>();

    public IList<IList<int>> Permute(int[] nums) 
    {
        Prune(new List<int>(), nums);

        return result;
    }

    public void Prune(IList<int> value, int[] nums)
    {
        List<int> valueCopy = new List<int>(value);

        if (nums.Length <= 1)
        {
            valueCopy.Add(nums[0]);
            result.Add(valueCopy);
            return;
        }
        
        for (int i = 0; i < nums.Length; i++)
        {
            valueCopy.Add(nums[i]);
            
            var numbersList = nums.ToList();
            numbersList.RemoveAt(i);
            Prune(valueCopy, numbersList.ToArray());
            valueCopy.RemoveAt(valueCopy.Count - 1);
        }
    }
}

해설: 재귀함수를 이용하여 BackTracking을 구현하였습니다.

1, 2, 3을 배치 후 기존에 valueCopy에서 있었던 2값을 삭제하고 그 위치에 다음 값인 3이 배치되고 남은 2가 마지막에 위치할 수 있도록하였습니다.

두번째 위치 값 변경이 완료되면 재귀로 돌아와 첫번째 값을 삭제하고 그 다음 숫자이 2가 첫번째 위치에 있도록 제작하였습니다.