[백준] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649

initial

This is a typical dfs backtracking problem that I struggled a little bit. I didn't know how to backtrack but the main important bit is

1) "return"ing when you have reached the main condition (like len(tmp)==m) for time efficiency so that you break out early
2) for backtracking, main logic is after dfs(), you marked visited[i] back to False for other DFS paths to traverse and path.pop() the last element of your path for other elements in the list to be traversed.

my correct solution

n,m= map(int,input().split())
lst = [i for i in range(1,n+1)]
tmp = []
visited = [False for _ in range(n)]

def dfs(tmp):
    if len(tmp)==m:
        formatted_string = ' '.join(map(str, tmp))
        print(formatted_string)
        return
    for i in range(len(lst)):
        if not visited[i]:
            tmp.append(lst[i])
            visited[i]=True
            dfs(tmp)
            visited[i]=False
            tmp.pop()

dfs(tmp)

other solution

They didnt use visited list but checked that visited condition via if i not in s where s is a list like my implementation.

n,m = list(map(int,input().split()))
 
s = []
 
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()

complexity

this is permutation so its m*p(n,m) time
for space, recursion stack is o(m) whole visited list is o(n) so space is n+m