Finding subsets with a sum of a number

Python solution

	arr=[5,4,8, 10,-4]
	k=6
	def check_if_sum_possible(arr, k):
	slate = []
	index = 0
	arrlen = 0
	if arr:
	arrlen = len(arr)
	def printSubset(index, slate):
	#base case
	if(index==arrlen):
	sum = 0
	if slate:
	for i in range(len(slate)):
	sum = sum + slate[i]
	if sum == k:
	print(slate, end=" ")
	return True
	else:
	return False
	return
	else:
	return False
	if(printSubset(index+1,slate)):
	return True
	slate.append(arr[index])
	if(printSubset(index+1,slate)):
	return True
	slate.pop()
	if(printSubset(index,slate)):
	return True
	return False
	print(check_if_sum_possible(arr, k))

view raw sumsets.py hosted with ❤ by GitHub

c++ solution

	#include<iostream>
	#include<vector>
	using namespace std;
	vector<int> bag = { 2, 8, -2 };
	int sum = 6, index=0;
	int bagSize;
	bool flag = false;
	bool printSubsetSums(int index , vector<int> slate){
	//basecase
	if(index == bagSize){
	cout << endl;
	int subsetSum = 0;
	int sizeSlate = slate.size();
	for (auto i : slate){
	//cout << i << " ";
	subsetSum = subsetSum + i;
	}
	if(subsetSum == sum){
	cout <<endl<<"sum found" <<endl;
	for (auto i : slate){
	cout << i << " ";
	}
	flag = true;
	return flag;
	}
	return flag;
	}
	//recursion
	printSubsetSums(index+1 , slate);
	slate.push_back(bag[index]);
	printSubsetSums(index+1, slate);
	slate.pop_back();
	}
	int main(){
	cout<< "Subset sums"<<endl;
	bagSize = bag.size();
	vector<int> slate ;
	printSubsetSums(index, slate) ;
	cout << std::boolalpha << flag;
	}

view raw subsetsums.cpp hosted with ❤ by GitHub

Dutch Flag problem

Dutch flag is a notable problem wherein you have a array representing three colors . Red(R), Green(G) and Blue(B) which needs to be sorted with Reds coming first followed by Green and then Blue. This is achieved by lumoto partitioning scheme.

	arr = ['G','B','R','G','B','G','R']
	ridx=0
	bidx=len(arr)-1
	i=0
	while(i<bidx):
	if(arr[i] == 'R'):
	arr[i],arr[ridx] = arr[ridx],arr[i]
	ridx += 1
	i = i+1
	elif (arr[i] == 'B'):
	arr[i],arr[bidx] = arr[bidx], arr[i]
	bidx -= 1
	else:
	i=i+1
	print(arr)

view raw dutchflag.py hosted with ❤ by GitHub

Printing out all combinations of string

Printing out all combinations of a string

	#! /bin/env/path python
	def printCombinations(slate,array):
	if (len(array)==0):
	print(slate)
	return
	printCombinations(slate,array[1:])
	printCombinations(slate+array[0], array[1:])
	printCombinations("", "abcd")

view raw Combinations.py hosted with ❤ by GitHub

Printing out all the permutations of string

How to generate permutation of a given string where digits are kept as it is, but alphabets are replaced by lower and upper case characters

	#! /usr/env/path python
	def helper(string, result, index , slate):
	if (len(string) == len(slate)):
	result.append(slate)
	return
	if(string[index].isdigit()):
	slate = slate + str(string[index])
	helper(string, result, index+1, slate)
	slate = slate[:-1]
	else:
	slate= slate + str(string[index].upper());
	helper(string, result, index+1, slate)
	slate = slate[:-1]
	slate = slate + str(string[index].lower())
	helper( string, result, index+1, slate)
	result =[]
	helper("a1b2",result, 0 , "")
	print(result)

view raw letterPermutationSort.py hosted with ❤ by GitHub

The above solution uses immutable strings so its not efficient time complexity-wise below solution replaces string with list

	#! /usr/env/path python
	''' This solution is done using list and removes the immutable
	string to avoid extra burden on time '''
	def solutions():
	result=[]
	def helper(index,slate=None):
	if slate== None:
	slate=[]
	if len(slate) == bag_len:
	result.append(''.join(slate))
	return
	if(bag[index].isdigit()):
	slate.append(bag[index])
	helper(index+1, slate)
	slate.pop()
	else:
	slate.append(str(bag[index].upper()))
	helper(index+1,slate)
	slate.pop()
	slate.append(str(bag[index].lower()))
	helper(index+1, slate)
	slate.pop()
	slate1 = list()
	bag = list("a1b2c3")
	bag_len = len(bag)
	helper( 0, slate1)
	print(result)
	solutions()

view raw strinnum.py hosted with ❤ by GitHub

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome. 

 Example 1: Input: head = [1,2,2,1] 

Output: true 

Example 2: Input: head = [1,2]

 Output: false 

 Constraints: The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9 

 Follow up: Could you do it in O(n) time and O(1) space?

	from collections import deque
	# 1->2->3->4->4->3->2->1
	# b b b b
	# f f f b
	# 1->2->3->4->5->4->3->2->1
	# b b b b b
	# f f f f f
	# Definition for singly-linked list.
	# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next
	class Solution:
	arr = []
	def isPalindrome(self, head: ListNode) -> bool:
	stack = deque()
	if (head == None):
	return False
	if (head.next == None):
	return True
	back = head
	front = head
	if(head.next.next == None):
	if(head.val == head.next.val):
	return True
	else:
	return False
	#store all values till mid in linked list to a stack
	while (front.next != None and front.next.next != None):
	stack.append(back.val)
	back = back.next
	front = front.next.next
	if(front.next == None):
	back = back.next
	else:
	temp = back.val
	if(back.next.val != temp):
	return False
	back = back.next.next
	while (back != None):
	poppedval = stack.pop()
	if back.val != poppedval :
	return False
	back = back.next
	return True

view raw palindrom_linkedlist.py hosted with ❤ by GitHub

Selection sort implementation in python

Here is a simple python implementation of selection sort. The asymptotic complexity of selection sort is n^2

	#usr/bin/env python
	arr = [1,3,6,7,4,6,8,9,1,4,6,7]
	for i in range(len(arr)):
	for j in range(i,len(arr)):
	if arr[j] < arr[i]:
	temp = arr[j]
	arr[j] = arr[i]
	arr[i] = temp
	print(arr)

view raw selection.py hosted with ❤ by GitHub