Skip to content

Instantly share code, notes, and snippets.

@shorttermmem
Created November 18, 2019 20:32
Show Gist options
  • Save shorttermmem/f51c88700e5f7afeb518830cec44b780 to your computer and use it in GitHub Desktop.
Save shorttermmem/f51c88700e5f7afeb518830cec44b780 to your computer and use it in GitHub Desktop.
def permute_all(a, l, r):
if l==r:
print("".join(a))
else:
for i in range(l,r+1):
a[l], a[i] = a[i], a[l]
permute_all(a, l+1, r)
a[l], a[i] = a[i], a[l] # backtrack
# Driver program to test the above function
string = "ABC1"
permute_all(list(string), 0, len(string)-1)
def letterCasePermutation(S: str) -> [str]:
if S == "": return [""]
ans = []
if S[0].isalpha():
for i in letterCasePermutation(S[1:len(S)]):
print(i)
ans.append(S[0].upper() + i)
ans.append(S[0].lower() + i)
else:
for i in letterCasePermutation(S[1:len(S)]):
ans.append(S[0] + i)
return ans
ans = letterCasePermutation("ABC2")
print(ans)
def subsetsUtil(A, subset, index, res):
res.append(subset)
#print(subset)
for i in range(index, len(A)):
# include the A[i] in subset.
subset.append(A[i])
# move onto the next element.
subsetsUtil(A, list(subset), i + 1, res)
# exclude the A[i] from subset and
# triggers backtracking.
subset.pop(-1)
return
# below function returns the subsets of vector A.
def subsets(A):
subset = []
res = []
# keeps track of current element in vector A
index = 0
subsetsUtil(A, subset, index, res)
print(res)
subsets("ABC3")
def printCombination(arr, r):
# A temporary array to
# store all combination
# one by one
data = [0]
# Print all combination
# using temprary array 'data[]'
combinationUtil(arr, data, 0, len(arr) - 1, 0, r)
# arr[] ---> Input Array
# data[] ---> Temporary array to
# store current combination
# start & end ---> Staring and Ending
# indexes in arr[]
# index ---> Current index in data[]
# r ---> Size of a combination to be printed
def combinationUtil(arr, data, start, end, index, r):
# Current combination is ready
# to be printed, print it
if (index == r):
for j in range(r):
print(data[j], end = " ")
print()
return
# replace index with all
# possible elements. The
# condition "end-i+1 >=
# r-index" makes sure that
# including one element at
# index will make a combination
# with remaining elements at
# remaining positions
i = start;
while(i <= end and end - i + 1 >= r - index):
data[index] = arr[i]
combinationUtil(arr, data, i + 1,
end, index + 1, r)
i += 1
#printCombination("ABC4", 2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment