15663_N과 M(9)

입력

첫째 줄에 수열 원소의 길이 N, 출력할 수열의 길이 M
둘째 줄에 수열의 원소를 입력받음

출력

가능한 모든 수열을 출력

조건

• 수열을 사전 순으로 출력
• 중복되는 수열은 출력하지 않음

풀이

수열을 사전 순으로 출력 => 수열의 원소를 오름차순으로 정렬
중복되는 수열은 출력하지 않음 => 동일한 원소인지 체크 & 이미 출력한 수열인지 체크

1. 입력받은 수열의 원소를 오름차순으로 정렬

list_ = list(map(int, sys.stdin.readline().split()))
list_.sort()

2. 수열(ans)를 이루는 원소가 중복되는지 확인 후 수열(ans)에 수열 원소 추가(list_[idx]) & check(동일한 원소가 있을 경우를 확인하기 위함)에 원소의 idx 추가
   
   추가 후 dfs 재귀

    for idx in range(0, N):
        if idx in check: continue
        ans.append(str(list_[idx]))
        check.append(idx)
        dfs()
        ans.pop()
        check.pop()

3. 수열(ans)의 길이가 M과 동일할 경우 check_ans에 동일한 수열이 존재하는지 확인 후 존재하지 않을 경우 출력 후 check_ans에 문자열 추가

    if len(ans) == M:
        tmp = ''.join(ans)
        check_ans.add(tmp)
        if check_ans_len != len(check_ans):
            print(*ans)
            check_ans_len += 1
        return

중복된 수열인지 확인하기 위해 처음에는 check_ans를 리스트로 생성 후 if ans in check_ans 로 확인하였지만 시간 초과 발생
check_ans를 set 으로 변경 후 길이를 확인하여 시간 초과 해결

전체 코드

N과 M(9)