leet

1st Trial : DFS를 통한 부분집합 구하기 + sum

1) modified Array 만들기
2) DFS를 이용하여 modified Array의 모든 부분집합 구하기
3) max Sum 구하기

class Solution(object):
    def kConcatenationMaxSum(self, arr, k):
        """
        
        :type arr: List[int]
        :type k: int
        :rtype: int
        
        """
        
        
        
        def DFS(L):
            
            if L == len(Arr)  :
                sumArr = 0
                # 모든 요소를 사용했을 때
                for i in range(L):
                    if ch[i] == 1:
                        sumArr += Arr[i]
                print("sum", sumArr)
                if sumArr > res[0] :
                    res[0] = sumArr
                
            else:
                # 아직 사용할 요소가 남아있을때
                # 해당 요소를 부분집합으로 사용할 때
                ch[L] = 1
                DFS( L + 1 )
                
                # 해당 요소를 사용하지 않을 때
                ch[L] = 0
                DFS ( L + 1 )
        
        # 모든 배열을 이어 붙이기
        Arr = []
        for i in range(k):
            Arr.extend(arr)
        Arr.insert(0,0) # 계산을 편하게 하기 위함
        
        print("Arr", Arr)
            
        # 해당 배열 요소에 대한 사용 여부
        ch = [0] * ( len(Arr) + 1) 
        res = [-12999312]
        DFS(1) 

        return res[0]