Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers.
Note: The generated output is printed without partitions. Each partition must be in decreasing order. Printing of all the partitions is done in reverse sorted order. 
Example 1:
Input: n = 3
Output: 3 2 1 1 1 1
Explanation: For n = 3, 
{3}, {2, 1} and {1, 1, 1}.
 
Example 2:
Input: n = 4 
Output: 4 3 1 2 2 2 1 1 1 1 1 1
Explanation: For n = 4, 
{4}, {3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}.
Your Task:
You don't need to read or print anything. Your task is to complete the function UniquePartitions() which takes n as input parameter and returns a list of all possible combinations in lexicographically decreasing order. 
 
Expected Time Complexity: O(2^n)
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 25

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Complete search

Starter code: #User function Template for python3



class Solution:

	def UniquePartitions(self, n):

		# Code here

Solutions:
class Solution:

	def util(self, a, n, S, s):
		global ans
		if S == 0:
			s = s[:-1]
			s = s.split(',')
			ans.append(s)
			return
		if n == 0:
			return
		if a[n - 1] <= S:
			self.util(a, n, S - a[n - 1], s + str(a[n - 1]) + ',')
			self.util(a, n - 1, S, s)
		else:
			self.util(a, n - 1, S, s)

	def UniquePartitions(self, n):
		global ans
		ans = []
		a = [i for i in range(1, n + 1)]
		self.util(a, n, n, '')
		return ans


class Solution:

	def UniquePartitions(self, n):
		dp = {1: ((1,),)}

		def recur(num):
			for i in range(2, num + 1):
				cur = [[i]]
				for j in range(1, i // 2 + 1):
					for k in dp[i - j]:
						cur.append(sorted(list(k) + [j], reverse=True))
				dp[i] = tuple(set(map(tuple, cur)))
		recur(n)
		return sorted(dp[n], reverse=True)


class Solution:

	def UniquePartitions(self, n):
		li = []

		def solve(i, target, li, temparr):
			if i <= 0:
				if target == 0:
					li.append(temparr[:])
				return
			if target > 0:
				temparr.append(i)
				solve(i, target - i, li, temparr)
				temparr.pop()
			solve(i - 1, target, li, temparr)
		solve(n, n, li, [])
		return li


class Solution:

	def UniquePartitions(self, n):
		arr = [i for i in range(n, 0, -1)]
		li = []

		def solve(i, target, arr, li, temparr):
			if i >= len(arr):
				if target == 0:
					li.append(temparr[:])
				return
			if target > 0:
				temparr.append(arr[i])
				solve(i, target - arr[i], arr, li, temparr)
				temparr.pop()
			solve(i + 1, target, arr, li, temparr)
		solve(0, n, arr, li, [])
		return li


class Solution:

	def UniquePartitions(self, n):
		dp = [[[1 + i]] for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				dp[i] += [[i - j] + partition for partition in dp[j] if partition[0] <= i - j]
		return dp[n - 1]


class Solution:

	def UniquePartitions(self, n):

		def fun(l, i, n):
			if n == 0:
				l1.append(l.copy())
				return l1
			if i < 1:
				return l1
			if i <= n:
				l.append(i)
				fun(l, i, n - i)
				l.pop()
				fun(l, i - 1, n)
			else:
				fun(l, i - 1, n)
		l1 = []
		l = []
		i = n
		fun(l, i, n)
		return l1


def rec(n, j):
	if n == 0:
		return [[]]
	c = []
	for i in range(1, j + 1):
		if n >= i:
			ans = rec(n - i, i)
			for k in ans:
				c.append([i] + k)
	return c

class Solution:

	def UniquePartitions(self, n):
		res = rec(n, n)
		res.sort(reverse=True)
		return res


class Solution:

	def UniquePartitions(self, n):

		def func(ind, tar, li, ds, ans):
			if ind == len(li):
				if tar == 0:
					ans.append(ds.copy())
				return
			if li[ind] <= tar:
				ds.append(li[ind])
				func(ind, tar - li[ind], li, ds, ans)
				ds.pop()
			func(ind + 1, tar, li, ds, ans)
		li = [i for i in range(n, 0, -1)]
		ds = []
		ans = []
		func(0, n, li, ds, ans)
		return ans


class Solution:

	def UniquePartitions(self, n):
		output = [[0]]
		for i in range(n, 0, -1):
			temp = []
			for item in output:
				j = 1
				temp2 = []
				while item[0] + j * i <= n:
					temp2.append(i)
					temp.append([item[0] + j * i] + item[1:].copy() + temp2.copy())
					j += 1
			output += temp
		return sorted([item[1:] for item in output if item[0] == n], reverse=True)


class Solution:

	def UniquePartitions(self, n):
		a = []
		for j in range(1, n + 1):
			a.append(j)
		a = a[::-1]
		ans = []

		def sub(i, s, su):
			if s == n:
				ans.append(su.copy())
				return
			if i >= n or s > n:
				return
			su.append(a[i])
			sub(i, s + a[i], su)
			su.pop()
			sub(i + 1, s, su)
		sub(0, 0, [])
		return ans


class Solution:

	def UniquePartitions(self, n):
		res = []
		nums = [i for i in range(1, n + 1)]

		def solve(target, n, arr):
			if target == 0:
				if arr not in res:
					res.append(arr)
				return
			if n < 0:
				return
			if nums[n - 1] <= target:
				arr1 = arr[:]
				arr1.append(nums[n - 1])
				solve(target - nums[n - 1], n, arr1)
				solve(target, n - 1, arr)
			else:
				solve(target, n - 1, arr)
		solve(n, n, [])
		return res


class Solution:

	def UniquePartitions(self, n):
		arr = []
		for i in range(n, 0, -1):
			arr.append(i)
		res = []

		def finder(arr, target, ind, path):
			if target == 0:
				res.append(path)
				return
			if ind == len(arr):
				return
			if target < 0:
				return
			finder(arr, target - arr[ind], ind, path + [arr[ind]])
			finder(arr, target, ind + 1, path)
		finder(arr, n, 0, [])
		return res


class Solution:

	def knapsack(self, n, val, i, arr, res, ans):
		if i >= n:
			if sum(ans) == n:
				j = ans.copy()
				j.sort(reverse=True)
				res.add(tuple(j))
			return
		if arr[i] <= val:
			self.knapsack(n, val - arr[i], i, arr, res, ans + [arr[i]])
			self.knapsack(n, val, i + 1, arr, res, ans)
		else:
			self.knapsack(n, val, i + 1, arr, res, ans)

	def UniquePartitions(self, n):
		arr = [x for x in range(1, n + 1)]
		res = set()
		self.knapsack(len(arr), n, 0, arr, res, [])
		res = sorted(list(res), reverse=True)
		return res


def backtracking(n):
	total = n
	stack = []
	res = []
	helper(n, total, stack, res)
	return res

def helper(n, total, stack, res):
	if not total:
		res.append(tuple(stack))
	for i in range(n, 0, -1):
		if total - i >= 0 and (not stack):
			stack.append(i)
			helper(n, total - i, stack, res)
			stack.remove(i)
		elif total - i >= 0 and stack[-1] >= i:
			stack.append(i)
			helper(n, total - i, stack, res)
			stack.remove(i)

class Solution:

	def UniquePartitions(self, n):
		return backtracking(n)


class Solution:

	def UniquePartitions(self, n):
		ans = []
		self.dfs(n, 0, [], ans)
		return ans

	def dfs(self, n, s, path, ans):
		if s == n:
			ans.append(path)
			return
		if s > n:
			return
		for i in range(n, 0, -1):
			if len(path) == 0 or path[-1] >= i:
				self.dfs(n, s + i, path + [i], ans)


a = []

def getArray(n, z, val):
	if n == 0:
		a.append(z)
	elif val <= 0 or n < 0:
		return -1
	else:
		getArray(n - val, z + [val], val)
		getArray(n, z, val - 1)

class Solution:

	def UniquePartitions(self, n):
		global a
		a = []
		getArray(n, [], n)
		return a


class Solution:

	def firstApproach(self, n):
		p = [0] * n
		k = 0
		p[k] = n
		res = []
		while True:
			res.append(p[0:k + 1])
			rem_val = 0
			while k >= 0 and p[k] == 1:
				rem_val += p[k]
				k -= 1
			if k < 0:
				return res
			p[k] -= 1
			rem_val += 1
			while rem_val > p[k]:
				p[k + 1] = p[k]
				rem_val = rem_val - p[k]
				k += 1
			p[k + 1] = rem_val
			k += 1

	def UniquePartitions(self, n):
		return self.firstApproach(n)


class Solution:

	def __init__(self):
		self.ans = []

	def f(self, W, n, arr, temp):
		if W == 0:
			self.ans.append(temp[0:])
			return
		if n < 0:
			return
		if arr[n] <= W:
			temp.append(arr[n])
			Solution.f(self, W - arr[n], n, arr, temp)
			temp.pop()
		Solution.f(self, W, n - 1, arr, temp)

	def UniquePartitions(self, n):
		arr = []
		for i in range(n):
			arr.append(i + 1)
		Solution.f(self, n, n - 1, arr, [])
		return self.ans


class Solution:

	def back_track(self, res, nums, i, target, found):
		if target < 0:
			return
		elif target == 0:
			res.append(found.copy())
		else:
			for j in range(i, n, 1):
				found.append(nums[j])
				self.back_track(res, nums, j, target - nums[j], found)
				found.remove(nums[j])
		return res

	def UniquePartitions(self, n):
		res = []
		nums = [i for i in range(n, 0, -1)]
		target = n
		self.back_track(res, nums, 0, target, [])
		return res


class Solution:

	def __init__(self):
		self.res = []
		self.sum1 = None

	def solve(self, n, pat, sum1):
		if sum1 > self.sum1 or n <= 0:
			return
		if sum1 == self.sum1:
			self.res.append(pat)
			return
		self.solve(n, pat + [n], sum1 + n)
		self.solve(n - 1, pat, sum1)

	def UniquePartitions(self, n):
		self.sum1 = n
		self.solve(n, [], 0)
		return self.res


class Solution:

	def dfs(self, n, s, l, m):
		if s == n:
			m.append(l)
			return
		if s > n:
			return
		for i in range(n, 0, -1):
			if len(l) == 0 or l[-1] >= i:
				self.dfs(n, s + i, l + [i], m)

	def UniquePartitions(self, n):
		m = []
		self.dfs(n, 0, [], m)
		return m


class Solution:

	def UniquePartitions(self, n):
		uparts = self.UniquePartitionsLow(n)
		upl = list(uparts)
		upl.sort(reverse=True)
		return upl

	def UniquePartitionsLow(self, n, memo={}):
		if 0 == n:
			return set()
		if n in memo:
			return memo[n]
		uparts = set()
		uparts.add((n,))
		if 1 == n:
			return uparts
		for k in range(1, n // 2 + 1):
			for upcl in self.UniquePartitionsLow(n - k, memo=memo):
				upl = [k]
				upl.extend(list(upcl))
				upl.sort(reverse=True)
				ups = tuple(upl)
				uparts.add(ups)
		memo.setdefault(n, uparts)
		return uparts


class Solution:

	def UniquePartitions(self, n):
		r = []

		def gorec(n, curr):
			if n == 0:
				r.append(curr.copy())
				return
			for i in range(n, 0, -1):
				if curr and curr[-1] < i:
					continue
				curr.append(i)
				gorec(n - i, curr)
				curr.pop()
		gorec(n, [])
		return r


class Solution:

	def UniquePartitions(self, n):

		def fun(n, arr=[], sum=0, partition=[]):
			if sum == n:
				arr.append(partition)
				return
			if sum > n:
				return
			for i in range(n, 0, -1):
				if len(partition) == 0 or partition[-1] >= i:
					fun(n, arr, sum + i, partition + [i])
			return arr
		return fun(n)


import sys
sys.setrecursionlimit(1000000)

def f(t, temp, res, last, N):
	if t == 0:
		c = temp[:]
		c.sort(reverse=True)
		res.append(c)
		return
	for i in range(last, n + 1):
		if i <= t:
			temp.append(i)
			f(t - i, temp, res, i, n)
			temp.pop()

class Solution:

	def UniquePartitions(self, n):
		res = []
		f(n, [], res, 1, n)
		res.sort(reverse=True)
		return res


class Solution:

	def UniquePartitions(self, n):
		ans = set()

		def f(ip, op=[]):
			if ip < 0:
				return
			if ip == 0:
				ans.add(tuple(sorted(op[:], reverse=True)))
				return
			for d in range(ip, 0, -1):
				if len(op) == 0 or op[-1] >= d:
					op.append(d)
					f(ip - d, op)
					op.remove(d)
		f(n)
		return sorted(ans, reverse=True)


class Solution:

	def helper(self, n, prev, current):
		if n == 0:
			self.finalAns.append(current[:])
			return
		for i in range(min(prev, n), 0, -1):
			current.append(i)
			self.helper(n - i, i, current)
			current.pop()

	def UniquePartitions(self, n):
		self.finalAns = []
		self.helper(n, float('inf'), [])
		return self.finalAns


class Solution:

	def UniquePartitions(self, k):
		dp = [[[] for j in range(k + 1)] for i in range(k + 1)]
		for i in range(k + 1):
			dp[0][i] = [[]]
		for i in range(1, k + 1):
			for j in range(1, k + 1):
				for g in dp[i][j - 1]:
					dp[i][j].append(g)
				if j <= i:
					for g in dp[i - j][j]:
						g_clone = g.copy()
						g_clone.append(j)
						dp[i][j].append(g_clone)
		for i in dp[-1][-1]:
			i.reverse()
		return dp[-1][-1][::-1]


class Solution:

	def UniquePartitions(self, n):
		res = []
		curr = []

		def dfs(n, prev):
			nonlocal res, curr
			if n == 0:
				res.append(curr.copy())
				return
			for i in range(min(prev, n), 0, -1):
				curr.append(i)
				dfs(n - i, i)
				curr.pop()
		dfs(n, n)
		return res


class Solution:

	def UniquePartitions(self, n):
		seq = [i for i in range(1, n + 1)]
		ans = []
		cur = []

		def partition(num, seq, n):
			nonlocal ans, cur
			if num == 0:
				for i in cur:
					ans.append([i])
				return
			elif n == 0:
				return
			if seq[n - 1] <= num:
				cur.append(seq[n - 1])
				partition(num - seq[n - 1], seq, n)
				cur.pop()
			partition(num, seq, n - 1)
			return
		partition(n, seq, n)
		return ans


class Solution:

	def __init__(self):
		self.ans = None

	def UniquePartitions(self, n):
		self.ans = []
		self.findAns(n, [], n)
		return self.ans

	def findAns(self, n, cur_list, mx):
		if n == 0:
			self.ans.append(cur_list.copy())
			return
		for v in range(min(mx, n), 0, -1):
			cur_list.append(v)
			self.findAns(n - v, cur_list, v)
			cur_list.pop()


class Solution:

	def solve(self, remSum, maxVal, idx, count, ans, dp):
		if remSum == 0:
			part = []
			for i in range(1, idx, 1):
				part.append(dp[i])
			ans.append(part)
			count += 1
			return
		i = maxVal
		while i >= 1:
			if i > remSum:
				i -= 1
				continue
			elif i <= remSum:
				dp[idx] = i
				self.solve(remSum - i, i, idx + 1, count, ans, dp)
				i -= 1

	def UniquePartitions(self, n):
		ans = []
		dp = [0 for i in range(200)]
		self.solve(n, n, 1, 0, ans, dp)
		return ans


import math

class Solution:

	def UniquePartitions(self, n):
		if n <= 1:
			return str(n)
		self.count = 1
		self.n = n
		max_len = self.n
		self.sequences = {i: [1] * max_len for i in range(1, n + 1)}
		level = 0
		self.start_partition()
		for i in range(n - 1, 1, -1):
			self.walk_down(i)
		combinations = [n] * self.count
		comb_idx = 1
		combinations[0] = [str(n)]
		for i in range(n - 1, 0, -1):
			idx = 1
			end_idx = self.sequences[i][0]
			while idx < end_idx:
				combinations[comb_idx] = map(str, self.sequences[i][idx])
				comb_idx += 1
				idx += 1
		return combinations

	def walk_down(self, number):
		index = 1
		max_index = self.sequences[number][0]
		while index < max_index:
			self.partition(number, index)
			index += 1
		return

	def start_partition(self):
		mid = self.n // 2
		if self.n % 2:
			mid += 1
		num = self.n - 1
		while num >= mid:
			num_list = self.sequences[num]
			num_list[num_list[0]] = [num, self.n - num]
			num_list[0] += 1
			self.count += 1
			num -= 1
		return

	def partition(self, number, index):
		number_list = self.sequences[number][index]
		number2 = number_list[1]
		num = 1
		mid = number // 2
		if number2 > mid:
			return
		while num <= mid:
			if num >= number2:
				num_list = self.sequences[number - num]
				lst_idx = num_list[0]
				if lst_idx >= len(num_list):
					num_list += [1] * self.n
				num_list[num_list[0]] = [number - num, num] + number_list[1:]
				num_list[0] += 1
				self.count += 1
			num += 1
		return


class Solution:

	def UniquePartitions(self, n):
		res = []
		array = [n - i for i in range(n)]

		def helper(arr, target, res, temp, index):
			if target == 0:
				res.append(temp)
				return
			if target < 0 or index == n:
				return
			helper(arr, target - arr[index], res, temp + [arr[index]], index)
			helper(arr, target, res, temp, index + 1)
		helper(array, n, res, [], 0)
		return res


class Solution:

	def UniquePartitions(self, n):
		table = [None] * (n + 1)
		table[0] = []
		table[1] = [[1]]
		for i in range(2, n + 1):
			res = [[i]]
			for j in range(i, 0, -1):
				for k in table[i - j]:
					if j >= k[0]:
						res.append([j] + k)
			table[i] = res
		return table[n]


class Solution:

	def UniquePartitions(self, n):
		dp = [0 for i in range(n)]
		count = 0
		ar = []

		def solve(remSum, maxVal, idx, count):
			if remSum == 0:
				a = []
				for i in range(idx):
					a.append(dp[i])
				ar.append(a)
				count += 1
				return
			i = maxVal
			while i >= 1:
				if i > remSum:
					i -= 1
					continue
				elif i <= remSum:
					dp[idx] = i
					solve(remSum - i, i, idx + 1, count)
					i -= 1
		solve(n, n, 0, 0)
		return ar


class Solution:

	def memoed(self, n, memo):
		if n == 0:
			return []
		if n == 1:
			return [[1]]
		if n in memo:
			return memo[n]
		res = [[n]]
		for i in range(n, 0, -1):
			for j in self.memoed(n - i, memo):
				if i >= j[0]:
					res.append([i] + j)
		memo[n] = res
		return memo[n]

	def UniquePartitions(self, n):
		return self.memoed(n, {})


class Solution:

	def UniquePartitions(self, n):
		partitions = [[n]]
		copier = [n]
		while copier[0] != 1:
			remainder = 0
			while copier[-1] == 1:
				remainder += copier.pop(-1)
			copier[-1] -= 1
			remainder += 1
			while remainder >= copier[-1]:
				copier.append(copier[-1])
				remainder -= copier[-1]
			if remainder != 0:
				copier.append(remainder)
			partitions.append(copier[:])
		return partitions


class Solution:

	def __init__(self):
		self.ans = []

	def fun(self, arr, i, target):
		if not target:
			self.ans.append(arr)
			return
		if i == 0:
			return
		if i <= target:
			self.fun(arr + [i], i, target - i)
		self.fun(arr, i - 1, target)
		return

	def UniquePartitions(self, n):
		i = n
		self.fun([], i, n)
		return self.ans


class Solution:

	def duplicate(self, lt):
		k = []
		for i in lt:
			if i not in k:
				k.append(i)
		return k

	def lexsort(self, lt):
		lt = sorted(lt, reverse=True)
		return lt

	def UniquePartitions(self, n):
		dict1 = {1: [[1]]}
		for i in range(2, n + 1):
			dict1[i] = []
			dict1[i].append([i])
			for j in range(i - 1, i // 2 - 1, -1):
				for k in dict1[j]:
					for h in dict1[i - j]:
						po = k + h
						dict1[i].append(sorted(po, reverse=True))
			dict1[i] = self.lexsort(self.duplicate(dict1[i]))
		ans = []
		for i in dict1[n]:
			ans.append(i)
		return ans


import copy

class Solution:
	ans = []
	v = []

	def find(total, i):
		global ans
		global v
		if total == 0:
			ans.append(copy.deepcopy(v))
			return
		if i == 0:
			return
		if i <= total:
			v.append(i)
			Solution.find(total - i, i)
			v.pop(-1)
		Solution.find(total, i - 1)

	def UniquePartitions(self, n):
		global ans
		global v
		ans = []
		v = []
		Solution.find(n, n)
		return ans


class Solution:

	def UniquePartitions(self, n):
		res = [[n]]
		arr = [n - i for i in range(n)]

		def helper(res, index, temp, _sum, arr):
			if _sum > n or index == n:
				return
			if sum(temp) == n:
				res.append(temp)
				return
			helper(res, index, temp + [arr[index]], _sum + arr[index], arr)
			helper(res, index + 1, temp, _sum, arr)
		helper(res, 1, [], 0, arr)
		return res


class Solution:

	def __init__(self):
		self.unique_parts = []

	def UniquePartitions(self, n):
		q = self.partitions(n, n, [])
		return self.unique_parts

	def partitions(self, curr_num, curr_sum, curr_part):
		if curr_sum < 0 or curr_num <= 0:
			return -1
		curr_part.append(curr_num)
		if curr_sum - curr_num == 0:
			self.unique_parts.append(curr_part[:])
		q = self.partitions(curr_num, curr_sum - curr_num, curr_part)
		curr_part.pop()
		q = self.partitions(curr_num - 1, curr_sum, curr_part)


class Solution:
	count = 0

	def UniquePartitions(self, n):
		table = [[[1]]] + [None] * (n - 1)
		for i in range(1, n):
			table[i] = [[i + 1]]
			for k in range(i):
				table[i].extend([[i - k] + l for l in table[k] if i - k >= l[0]])
		return table[-1]


class Solution:

	def UniquePartitions(self, n):
		ans = []

		def printArray(p, n, ans):
			res = []
			for i in range(0, n):
				res.append(p[i])
			ans.append(res)
			return ans
		p = [0] * n
		k = 0
		p[k] = n
		while True:
			ans = printArray(p, k + 1, ans)
			rem_val = 0
			while k >= 0 and p[k] == 1:
				rem_val += p[k]
				k -= 1
			if k < 0:
				break
			p[k] -= 1
			rem_val += 1
			while rem_val > p[k]:
				p[k + 1] = p[k]
				rem_val = rem_val - p[k]
				k += 1
			p[k + 1] = rem_val
			k += 1
		return ans


class Solution:

	def UniquePartitions(self, n):
		curr = []
		a = []
		for i in range(n, 0, -1):
			a.append(i)
		res = []

		def backtr(i, su):
			if su == n:
				res.append(curr.copy())
				return
			if i >= n or su > n:
				return
			curr.append(a[i])
			backtr(i, su + a[i])
			curr.pop()
			backtr(i + 1, su)
			return res
		return backtr(0, 0)


class Solution:

	def UniquePartitions(self, n):

		def helper(n, x, l, temp):
			if x == n:
				temp.append(l)
				return
			if x > n:
				return
			for i in range(n, 0, -1):
				if len(l) == 0 or l[-1] >= i:
					helper(n, x + i, l + [i], temp)
		ans = []
		helper(n, 0, [], ans)
		return ans


class Solution:

	def UniquePartitions(self, n):
		all_p = []

		def partition(k, m, parts):
			if k == 0:
				return parts
			return_parts = []
			for j in range(min(k, m), 0, -1):
				next_parts = parts.copy()
				next_parts.append(j)
				return_parts = return_parts + partition(k - j, j, next_parts)
			return return_parts
		for i in range(n, 0, -1):
			all_p.append(partition(n - i, i, [i]))
		return all_p