consideration of permutations.

permutations.py

'''
link
 - https://leetcode.com/problems/permutations/

problem:
    Given a collection of distinct integers, return all possible permutations.
    Example:
        Input: [1,2,3]
        Output:
        [
          [1,2,3],
          [1,3,2],
          [2,1,3],
          [2,3,1],
          [3,1,2],
          [3,2,1]
        ]
'''
# solution 1
def dfs1(nums, path, ans):
    if len(nums) == 0:
        ans.append(path)

    for i in range(len(nums)):
        dfs1(nums[:i]+nums[i+1:], path+[nums[i]], ans)

def main1():
    result = []
    nums = [1, 2, 3]
    dfs1(nums, [], result)
    print(result)

if __name__ == '__main__':
    main1()
    
# solution 2
def dfs2(nums):
    ans = []
    if len(nums) == 1:
        return [[]]
    
    for i in range(len(nums)):
        for sub in dfs2(nums[:i]+nums[i+1:]):
            ans.append(sub+[nums[i]])
            
    return ans

def main2():
    nums = [1, 2, 3]
    result = dfs2(nums) 
    print(result)
    
if __name__ == '__main__':
    main2()

'''
link
 - https://leetcode.com/problems/subsets/

problem:
    Given a set of distinct integers, nums, return all possible subsets (the power set).
    Note: The solution set must not contain duplicate subsets.
    Example:
        Input: nums = [1,2,3]
        Output:
            [
              [3],
              [1],
              [2],
              [1,2,3],
              [1,3],
              [2,3],
              [1,2],
              []
            ]
'''
# solution A
def  dfsA(nums, sets):
    if len(nums) == 0:
        return
        
    e = nums.pop()
    
    subsets = list(sets)
    
    for s in subsets:
        sets.append(s+[e])
        
    dfsA(nums, sets)

def mainA():
    result = [[]]
    nums = [1, 2, 3]
    dfsA(nums, result)
    print(result)
    
if __name__ == '__main__':
    mainA()
    
# solution B
def dfsB(nums):
    ans = []
    if len(nums) == 1:
        return [nums]
    
    e = nums.pop()
    ans.append([e])
    
    for sub in dfsB(nums):
        ans.extend([sub, [e]+sub])

    return ans

def mainB():
    nums = [1, 2, 3]
    result = dfsB(nums) + [[]]
    print(result)
    
if __name__ == '__main__':
    mainB()