[백준] 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

Time Complexity:

• The DFS function is called recursively for each possible combination.
• At each level of recursion, you consider each element in the list lst, and you explore all possible combinations.
• In the worst case, you will have n choices at the first level, n-1 choices at the second level, and so on.
• Therefore, the time complexity is O(n n-1 n-2 ... (n-m+1)), which is roughly O(n^m). This is because, in the worst case, you are exploring all possible combinations of size m from a list of n elements.

Space Complexity:

• The primary data structures contributing to space complexity are the tmp list, visited list, and the recursive call stack.
• The tmp list stores the current combination, and its maximum size can be m, so the space complexity is O(m).
• The visited list stores whether an element has been visited or not, which also has a maximum size of n, so the space complexity is O(n).
• The recursive call stack can have a maximum depth of m, as you are making recursive calls for each element in the combination, so the space complexity for the call stack is O(m).
• Overall, the space complexity is O(n + m + m) = O(n + 2m), which can be approximated to O(n) if n is much larger than m.

In summary, the time complexity of your code is roughly O(n^m), and the space complexity is O(n) in most practical cases, assuming n is significantly larger than m.