[백준] 15663번: N과 M (9)

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

initial

my wrong initial attempt. question asked to print when each dfs search is finisehd but i stored all the answer in a set and printed out in 1 go.

btw I used a list to practise dfs and append list to list.

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

def dfs(tmp):
    if len(tmp)==m:
        ans.append(tmp.copy())
        return
    for i in range(len(lst)):
        if not visited[i]:
            visited[i]=True
            tmp.append(lst[i])
            dfs(tmp)
            tmp.pop()
            visited[i]=False
dfs(tmp)
hola = set()
for i in ans:
    hola.add(' '.join(map(str,i)))
hola = list(hola)
hola.sort()
for i in hola:
    print(i)

so let's correct it

model solution much better (below mine)

n,m = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()
visited = [False for _ in range(n)]
tmp = []
hola = set()

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

but it is not that time and space efficient because im checking each time if that stored value is inside our set or not. But if we just check if the incoming value is different from the previous value, we can do it better timewise and spacewise

n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))
visited = [False] * n
temp = []

def dfs():
    if len(temp) == m:
        print(*temp)
        return
    remember_me = 0
    for i in range(n):
        if not visited[i] and remember_me != nums[i]:
            visited[i] = True
            temp.append(nums[i])
            remember_me = nums[i]
            dfs()
            visited[i] = False
            temp.pop()

dfs()

revisited aug 22nd

so this is permutation so instead of passing idx+1 as parameter to dfs, we need a visited list

complexity

my solution is

Time Complexity:

• In the dfs function, you have a loop that iterates over the elements of lst.
• At each step, you make recursive calls and backtrack.
• The total number of recursive calls made is dependent on the size of lst and m, but it is not strictly exponential because you're using backtracking to prune the search.
• The time complexity can be described as O(N choose M), which represents the number of combinations of N elements taken M at a time. This is essentially a combinatorial problem and is less than O(N^M) but still can grow significantly for large values of N and M.

Space Complexity:

• The primary contributors to space complexity are the tmp list, the visited list, and the hola set.
• The tmp list stores the current combination and can have a maximum length of m, so its space complexity is O(m).
• The visited list tracks whether an element has been visited or not, and its size is equal to the size of lst, so its space complexity is O(n).
• The hola set is used to store unique combinations. In the worst case, it can contain all valid unique combinations, so its space complexity depends on the number of unique combinations generated, which can be significant.
• Overall, the space complexity is O(n + m + unique combinations), and the most significant factor is the number of unique combinations.

In summary, the time complexity is determined by the number of unique combinations generated (less than exponential) and the space complexity depends on the number of unique combinations as well. The code efficiently prunes duplicate combinations by using the hola set to store and check for uniqueness.