LeetCode/Permutations

백트래킹은 항상 어렵다. 익숙하지 않아서 인듯

아래에 설명이 잘 되어있다.

https://leetcode.com/problems/permutations/discuss/1961596/C%2B%2B-oror-Easy-to-Understand-with-Diagram-oror-0-ms-oror-Backtracking

눈여겨 보아야 할 점은 j는 i부터 시작이라는 점이다. 즉, 자기자신과 swap을 함으로써 모든 경우를 포함시킨다.

123을 생각해보면

for 루프를 돌면서

123 213 321 을 tracking함수에 num으로 넘기고 i는 1이 된다.

123을 생각해보면 j=i, 즉 1인 상태에서 swap 123

2인 상태에서 132 가 된다. 이제 i를 2로 만들어서 넘기면 if문에 의해 123 132가 res에 담긴다.

213 321도 마찬가지이다.

전체적인 순서를 다시 봐보면

123을 넘겨받고 i는 0인 상태에서 0과 0번째를 swap해서 123을 만들고 tracking함수에 넘긴 뒤 재귀가 끝나면 다시 원래대로 복귀시킨다. 그래서 213으로 만들어서 재귀 돌린뒤, 다시 123으로 만들어 다음 루프에서 321로 되도록 한다.

class Solution {
	public:
		void tracking(vector<vector<int>> &res , vector<int> &nums,int i){
			if(i==nums.size()){
				res.push_back(nums);
				return;
			}
		for(int j=i;j<nums.size();j++){
		   swap(nums[i],nums[j]);
		   tracking(res,nums,i+1);
		   swap(nums[i],nums[j]);
		}
			return;
		}
		vector<vector<int>> permute(vector<int>& nums) {
			vector<vector<int>> res;
			tracking(res,nums,0);
			return res;
		}
	};