# O(n^3)
import itertools

def substring(s):
    substrings = []
    for i in range(len(s)):
        for j in range(i + 1, len(s)+1):
            substrings.append(s[i:j])
    return substrings

# O(2^N)
def subset(s):
    store = []
    running = []
    def helper(s, index, running, store):
        if index == len(s):
            store.append("".join(running))
            return
        running.append(s[index])
        helper(s, index + 1, running, store)
        running.pop()
        helper(s, index + 1, running, store)
    helper(s, 0, running, store)
    return store

# O(N!)
def permutation(s):
    #print(s)
    if len(s) == 1:
        return [s]
    base = s[0]
    array = permutation(s[1:])
    newarray = []
    for word in array:
        for i in range(len(word)+1):
            addedword = word[:i] + base + word[i:]
            newarray.append(addedword)
    #print(newarray)
    return newarray

# O(N!)
def combination(s, r):
    visited = set()
    running, store = [], []
    def helper(s, index, r, visited, running, store):
        if len(running) == r:
            store.append("".join(running))
            return
        if len(s) == index:
            return
        for i in range(index, len(s)):
            if i not in visited:
                running.append(s[i])
                visited.add(i)
                helper(s, index + 1, r, visited, running, store)
                running.pop()
                visited.discard(i)
    helper(s, 0, r, visited, running, store)
    return store

s = "abc"
#s = "stackover"
print(substring(s))
print(subset(s))
print(combination(s, 3))
print(combination(s, 2))
print(combination(s, 1))
print(permutation(s))

print("PYHTON itertools library ")
import itertools
import math

print("PERMUTATION For array :3P3")
print(math.factorial(3))
print(list(itertools.permutations([1,2,3])))

print("PERMUTATION [1,2,3], 2 :3P2")
print(math.factorial(3)//math.factorial(3-2))
print(list(itertools.permutations([1,2,3],2)))

print("PERMUTATION [1,2,3], 1 : 3P1")
print(math.factorial(3)//math.factorial(3-1))
print(list(itertools.permutations([1,2,3],1)))

print("COMBINATION [1,2,3], 3 : 3C3")
print(math.factorial(3)//(math.factorial(3-3)*math.factorial(3)))
print(list(itertools.combinations([1,2,3], 3)))

print("COMBINATION [1,2,3], 2 : 3C2")
print(math.factorial(3)//(math.factorial(3-2)*math.factorial(2)))
print(list(itertools.combinations([1,2,3],2)))

print("COMBINATION [1,2,3], 1 : 3C1")
print(math.factorial(3)//(math.factorial(3-1)*math.factorial(1)))
print(list(itertools.combinations([1,2,3],1)))


def nPr(n, r):
    return int(math.factorial(n)//math.factorial(n-r))

def nCr(n, r):
    return int(math.factorial(n)/(math.factorial(n-r)*math.factorial(r)))