모든조합

  • 배열로 원소가 나열되어있을때 이 원소들을 조합해서 만드는 경우를 출력
  • 중복으로 사용하지 않고, 조합할때 순서가 필요할때 사용가능
    • abc,acb와 같은 경우들 포함됨

간단 설명

  • 재귀를 사용
    • 일부 문제에서는 시간초과가 날 수 있음
  • 예시
    • [a,b,c]라고 되어있을때
    • 모든 조합은 a,b,c,ab,ac,abc,acb,ba,bc,bac,bca,ca,cb,cab,cba로 총 15개가 나타난다.

코드

# 조합을 위한 배열 inputList
# 사용여부를 확인하기위한 check
# 결과 저장용 save
inputList = ["a","b","c"]
check = [0]*len(inputList) # 0은 사용안됨, 1은 사용됨
save = []
allcheck(inputList,check,[],save)

def allcheck(inputList,check,result,save):
    # [배열,해당배열사용여부,만들어지는숫자,결과저장]
    # result의 길이 확인
        # result가 ls와 길이가 같으면 종료
    if len(result)>0 and len(result)<=len(inputList):
        # 만들어진 result가 0보다 크고, 주어진 배열요소(inputList)보다 작거나 같을때
        # save에 저장
        save.append(result)
    for i,c in enumerate(check):
        # check를 통해 사용여부 확인 0인것만 이용
        if c==0:# 사용안됨
            # result에 해당 숫자 추가
            resultTmp = result[:]
            resultTmp.append(inputList[i])
            # check에 숫자 사용한거 표시
            checkTmp = check[:]
            checkTmp[i]=1
            allcheck(inputList,checkTmp,resultTmp,save)

사용된곳

  • https://programmers.co.kr/learn/courses/30/lessons/42839