백트래킹 문제 폐관수련의 시작을 알리는 문제였다. 리트코드에서 백트래킹/dfs 위주 문제들을 주로 풀었으면서 최대한 이해할려했고 문제를 풀면서도 많이 배우고 있는중이다. 이번 문제는 이어지는 숫자들이 k만큼의 차이를 가지고있고 n만큼의 길이를 가지고있는 모든 조합들을 담은 벡터를 리턴하면 되는문제였다. 다만 주의 할점은 0이 처음 숫자로 나오면 안되는점.
이 문제를 보고나서 바로 생각이 들었던 두가지가 있었다. 숫자간의 차이를 k만큼 나오기 위해 abs() 함수를 이용하여 절대값을 이용하고 0...9까지 숫자를 하나씩만 사용하는게 아닌 하나의 숫자를 여러번 사용할수 있어야한다는점. 예) 181 k = 7. 이런류의 문제는 기존에 사용하던 Combination 방법을 쓰는게 아니고 Permutation 방법을 써줘야한다 생각했다. 그렇다고 Visited 벡터는 따로 사용하지 않은 이유는 만약 k가 0일때 888같이 본인을 포함한 여러 숫자를 리턴해야할수도 있기 때문이다.
제일 첫번째로 Combination 방법과는 다르게 i를 임의에 인덱스 변수로 지정해주는게 아닌 항상 0부터 시작할수있게 하였다. 다만, 가장 첫번째 숫자가 0이 되면 안되기에 if 문에서는 s라는 스트링 변수가 비어있지 않고 i가 0이 아닐때를 조건부로 썼다. 그리고 지금까지 있는 s의 마지막 숫자와 현제 i가 가리키는 숫자의 절대값을 찾았을때 k값이면은 s에 추가했고 dfs를 하였다.
이런 완전탐색을 진행하면 나중에는 s가 n만큼의 길이가 되었을때 답에다가 포함시키면 끝이난다.
배운점:
- char 을 int 로 바꾸고 싶을때는 char - '0'하면된다
- 반대로 int 를 char 로 바꾸고 싶을때는 int + '0' 하면된다
- Permutation의 원리를 잘 이해하자
