Given an array arr[] of length n. Find all possible unique permutations of the array.
Example 1:
Input: 
n = 3
arr[] = {1, 2, 1}
Output: 
1 1 2
1 2 1
2 1 1
Explanation:
These are the only possible unique permutations
for the given array.
Example 2:
Input: 
n = 2
arr[] = {4, 5}
Output: 
4 5
5 4
Your Task:
You don't need to read input or print anything. You only need to complete the function uniquePerms() that takes an integer n, and an array arr of size n as input and returns a sorted list of lists containing all unique permutations of the array.
Expected Time Complexity:  O(n*n!)
Expected Auxilliary Space: O(n*n!)
 
Constraints:
1 ≤ n ≤ 9
1 ≤ arr_{i} ≤ 10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3

class Solution:
    def uniquePerms(self, arr, n):
        # code here 

Solutions:
def permutations(s, n, ans, subs, freq, k):
	if k == n:
		ans.append(subs[:])
		return
	i = 0
	while i < n:
		if i != 0 and s[i] == s[i - 1] and (freq[i - 1] == 0):
			i += 1
			continue
		if freq[i] == 0:
			subs.append(s[i])
			freq[i] = 1
			k += 1
			permutations(s, n, ans, subs, freq, k)
			k -= 1
			freq[i] = 0
			subs.pop()
		i += 1

class Solution:

	def uniquePerms(self, S, n):
		S.sort()
		ans = []
		subs = []
		freq = [0] * n
		k = 0
		permutations(S, n, ans, subs, freq, k)
		return ans


class Solution:

	def uniquePerms(self, arr, n):
		res = []
		perm = []
		count = {x: 0 for x in arr}
		for x in arr:
			count[x] += 1

		def dfs():
			if len(perm) == len(arr):
				res.append(perm.copy())
				return
			for x in count:
				if count[x] > 0:
					perm.append(x)
					count[x] -= 1
					dfs()
					count[x] += 1
					perm.pop()
		dfs()
		return res


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		res = []
		for perm in sorted(set(permutations(arr))):
			res.append(list(perm))
		return res


class Solution:

	def uniquePerms(self, arr, n):
		nums = arr
		from collections import defaultdict
		dict = defaultdict(int)

		def perm(ind, nums, ans, dict):
			if ind == len(nums):
				if dict[str(nums)] == 0:
					dict[str(nums)] += 1
					ans.append(nums[:])
				return
			for i in range(ind, len(nums)):
				swap(i, ind, nums)
				perm(ind + 1, nums, ans, dict)
				swap(i, ind, nums)

		def swap(i, ind, nums):
			a = nums[i]
			nums[i] = nums[ind]
			nums[ind] = a
		ans = []
		ind = 0
		perm(ind, nums, ans, dict)
		return sorted(ans)


class Solution:

	def uniquePerms(self, nums, n):
		res = []
		s = []
		count = {n: 0 for n in nums}
		for n in nums:
			count[n] += 1

		def solve():
			if len(s) == len(nums):
				res.append(s.copy())
			for n in count:
				if count[n] > 0:
					s.append(n)
					count[n] -= 1
					solve()
					count[n] += 1
					s.pop()
		solve()
		return res


class Solution:

	def uniquePerms(self, arr, n):
		li = set()
		indxarr = [True for i in range(n)]

		def solve(arr, li, indxarr, temparr):
			if len(temparr) == len(arr):
				li.add(tuple(temparr))
				return
			for i in range(len(arr)):
				if indxarr[i]:
					indxarr[i] = False
					temparr.append(arr[i])
					solve(arr, li, indxarr, temparr)
					indxarr[i] = True
					temparr.pop()
		solve(arr, li, indxarr, [])
		li = sorted(list(li))
		return li


class Solution:

	def recur(self, arr, start, end, ans, vis):
		if start == end and tuple(arr) not in vis:
			ans.append(arr.copy())
			vis.add(tuple(arr))
		else:
			for i in range(start, end):
				self.swap(arr, start, i)
				self.recur(arr, start + 1, end, ans, vis)
				self.swap(arr, start, i)

	def swap(self, arr, start, end):
		(arr[start], arr[end]) = (arr[end], arr[start])

	def uniquePerms(self, arr, n):
		ans = []
		vis = set()
		self.recur(arr, 0, n, ans, vis)
		ans.sort()
		return ans


from collections import defaultdict

class Solution:

	def uniquePerms(self, arr, n):
		cnts = defaultdict(int)
		for num in arr:
			cnts[num] += 1
		return self.helper(cnts, n)

	def helper(self, cnts, n):
		if n == 0:
			return [[]]
		res = []
		for (num, cnt) in cnts.items():
			if cnt == 0:
				continue
			cnts[num] -= 1
			for sub_res in self.helper(cnts, n - 1):
				sub_res.insert(0, num)
				res.append(sub_res)
			cnts[num] += 1
		return res


class Solution:

	def solve(self, arr, res, i, out):
		if len(arr) == 0:
			res.append(tuple(out.copy()))
			return
		for j in range(len(arr)):
			curr = arr[j]
			newarr = arr[:j]
			newarr += arr[j + 1:]
			out.append(curr)
			self.solve(newarr, res, i + 1, out)
			out.pop()

	def uniquePerms(self, arr, n):
		res = []
		self.solve(arr, res, 0, [])
		res = set(res)
		res = list(res)
		res.sort()
		return res


def permute(arr, l, r, res, vis):
	if l == r:
		res.append(arr.copy())
	else:
		s = set()
		for i in range(l, r):
			if arr[i] in s:
				continue
			s.add(arr[i])
			(arr[l], arr[i]) = (arr[i], arr[l])
			permute(arr, l + 1, r, res, vis)
			(arr[l], arr[i]) = (arr[i], arr[l])

class Solution:

	def uniquePerms(self, arr, n):
		vis = set()
		res = []
		permute(arr, 0, n, res, vis)
		res.sort()
		return res


def permute(arr, l, r, res, vis):
	if l == r and tuple(arr) not in vis:
		vis.add(tuple(arr))
		res.append(tuple(arr))
	else:
		for i in range(l, r):
			(arr[l], arr[i]) = (arr[i], arr[l])
			permute(arr, l + 1, r, res, vis)
			(arr[l], arr[i]) = (arr[i], arr[l])

class Solution:

	def uniquePerms(self, arr, n):
		vis = set()
		res = []
		permute(arr, 0, n, res, vis)
		res.sort()
		return res


def uniq(arr, ans, ind, n, res):
	if ind == n:
		ans = tuple(ans)
		res.append(ans)
		return
	for i in range(len(arr)):
		ans.append(arr[i])
		uniq(arr[0:i] + arr[i + 1:], ans.copy(), ind + 1, n, res)
		ans.pop()

class Solution:

	def uniquePerms(self, arr, n):
		ans = []
		res = []
		ind = 0
		uniq(arr, ans, ind, n, res)
		res = list(set(res))
		res.sort()
		return res


class Solution:

	def uniquePerms(self, arr, n):
		ans = []

		def find(arr, temp=[]):
			if len(arr) == 0:
				ans.append(temp)
				return
			uset = set()
			for i in range(len(arr)):
				if arr[i] in uset:
					continue
				uset.add(arr[i])
				t = arr[:i] + arr[i + 1:]
				find(t, temp + [arr[i]])
		find(arr)
		return sorted(ans)


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		return sorted(set(permutations(arr)))


from typing import List
import itertools

class Solution:

	def dfs(self, a: List[int], pos: int, ans: List[List[int]], n: int) -> None:
		if pos == n:
			ans.append(a.copy())
			return
		for i in range(pos + 1, n):
			if a[i] != a[pos]:
				(a[i], a[pos]) = (a[pos], a[i])
				self.dfs(a, pos + 1, ans, n)
				(a[i], a[pos]) = (a[pos], a[i])
		self.dfs(a, pos + 1, ans, n)

	def uniquePerms(self, arr: List[int], n: int) -> List[List[int]]:
		ans = []
		self.dfs(arr, 0, ans, n)
		ans = sorted(ans)
		ans = list((k for (k, _) in itertools.groupby(ans)))
		return ans


class Solution:

	def uniquePerms(self, arr, n):
		cur = []
		ans = []
		visited = [0] * n
		arr = sorted(arr)

		def backtrack():
			nonlocal cur, ans, arr, n, visited
			if len(cur) == n:
				ans.append(cur[:])
				return
			for i in range(n):
				if visited[i]:
					continue
				if i > 0 and arr[i] == arr[i - 1] and (visited[i - 1] == 0):
					continue
				visited[i] = 1
				cur.append(arr[i])
				backtrack()
				visited[i] = 0
				del cur[-1]
			return
		backtrack()
		return ans


class Solution:

	def helper(self, ind, n, arr, ans):
		if ind == n:
			ans.append(arr[:])
			return
		s = set()
		for i in range(ind, n):
			if arr[i] not in s:
				s.add(arr[i])
				(arr[i], arr[ind]) = (arr[ind], arr[i])
				self.helper(ind + 1, n, arr, ans)
				(arr[i], arr[ind]) = (arr[ind], arr[i])

	def uniquePerms(self, arr, n):
		ans = []
		self.helper(0, n, arr, ans)
		return sorted(ans)


class Solution:

	def shouldSwap(self, start, curr, arr):
		for i in range(start, curr):
			if arr[i] == arr[curr]:
				return False
		return True

	def helper(self, ind, n, arr, ans):
		if ind == n:
			ans.append(arr[:])
			return
		for i in range(ind, n):
			if self.shouldSwap(ind, i, arr):
				(arr[i], arr[ind]) = (arr[ind], arr[i])
				self.helper(ind + 1, n, arr, ans)
				(arr[i], arr[ind]) = (arr[ind], arr[i])

	def uniquePerms(self, arr, n):
		ans = []
		self.helper(0, n, arr, ans)
		return sorted(ans)


class Solution:

	def uniquePerms(self, arr, n):
		s = []
		arr.sort()

		def recurs(i, s):
			if i == n:
				s.append(arr[:])
				return
			for ind in range(i, n):
				(arr[i], arr[ind]) = (arr[ind], arr[i])
				recurs(i + 1, s)
				(arr[i], arr[ind]) = (arr[ind], arr[i])
		recurs(0, s)
		s.sort()
		ans = []
		for i in s:
			if not ans or ans[-1][:] != i[:]:
				ans.append(i)
		return ans


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		l = []
		s = set(permutations(arr))
		for i in s:
			l.append(i)
		return sorted(l)


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		result = []
		ans = set(permutations(arr))
		for i in ans:
			result.append(i)
		return sorted(result)


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		res = set()
		for i in permutations(arr):
			res.add(i)
		res = list(res)
		res.sort()
		return res


class Solution:

	def uniquePerms(self, arr, n):
		ans = []

		def solve(i, arr, ans, n):
			if i == n:
				ans.append(arr.copy())
				return
			s = set()
			for j in range(i, n):
				if arr[j] in s:
					continue
				s.add(arr[j])
				(arr[i], arr[j]) = (arr[j], arr[i])
				solve(i + 1, arr, ans, n)
				(arr[i], arr[j]) = (arr[j], arr[i])
		solve(0, arr, ans, n)
		return sorted(ans)


class Solution:

	def uniquePerms(self, a, n):
		l = []
		d = {}

		def dfs(p, q, x):
			if x == 0:
				if not d.get(tuple(q), False):
					l.append(q[:])
					d[tuple(q)] = True
				return
			for i in range(x):
				q.append(p.pop(i))
				dfs(p, q, x - 1)
				p.insert(i, q.pop(-1))
		dfs(a, [], n)
		return sorted(l)


class Solution:

	def swap(self, i, index, nums):
		temp = nums[i]
		nums[i] = nums[index]
		nums[index] = temp

	def findAllPermutations(self, index, nums, ans):
		if index == len(nums):
			ds = []
			for i in range(len(nums)):
				ds.append(nums[i])
			if ds not in ans:
				ans.append(ds)
				return
			return
		for i in range(index, len(nums)):
			self.swap(i, index, nums)
			self.findAllPermutations(index + 1, nums, ans)
			self.swap(i, index, nums)

	def uniquePerms(self, nums, n):
		ans = []
		self.findAllPermutations(0, nums, ans)
		ans.sort()
		return ans

class Solution:

	def uniquePerms(self, nums, n):
		results = []

		def backtrack(pointer):
			if pointer == len(nums):
				results.append(nums[:])
				return
			seen = set()
			for i in range(pointer, len(nums)):
				if nums[i] not in seen:
					seen.add(nums[i])
					(nums[i], nums[pointer]) = (nums[pointer], nums[i])
					backtrack(pointer + 1)
					(nums[i], nums[pointer]) = (nums[pointer], nums[i])
		backtrack(0)
		results.sort()
		return results


class Solution:

	def uniquePerms(self, nums, n):
		results = []

		def backtrack(pointer):
			if pointer == len(nums):
				results.append(nums[:])
				return
			seen = set()
			for i in range(pointer, len(nums)):
				if nums[i] not in seen:
					seen.add(nums[i])
					(nums[i], nums[pointer]) = (nums[pointer], nums[i])
					backtrack(pointer + 1)
					(nums[i], nums[pointer]) = (nums[pointer], nums[i])
		backtrack(0)
		results.sort()
		return results


class Solution:

	def recursion(self, a, ind, ans):
		if ind == len(a):
			ans.append(a.copy())
			return
		for i in range(ind, len(a)):
			(a[i], a[ind]) = (a[ind], a[i])
			self.recursion(a, ind + 1, ans)
			(a[i], a[ind]) = (a[ind], a[i])

	def uniquePerms(self, arr, n):
		ans = []
		self.recursion(arr, 0, ans)
		p = sorted(set(map(tuple, ans)))
		return p


class Solution:

	def recurrsion(self, list1, list2, arr, n, hash1):
		if len(list1) == len(arr):
			list2.append(list1.copy())
			return
		for n in hash1:
			if hash1[n] > 0:
				list1.append(n)
				hash1[n] -= 1
				self.recurrsion(list1, list2, arr, n, hash1)
				list1.pop()
				hash1[n] += 1
		return list2

	def uniquePerms(self, arr, n):
		list1 = []
		list2 = []
		hash1 = {}
		hash1 = {n: 0 for n in arr}
		for n in arr:
			hash1[n] += 1
		self.recurrsion(list1, list2, arr, n, hash1)
		return list2


from itertools import permutations as per

class Solution:

	def uniquePerms(self, arr, n):
		ans_lis = []
		set_ans = set(per(arr))
		for i in set_ans:
			ans_lis.append(i)
		return sorted(ans_lis)


from itertools import permutations

class Solution:

	def solve(self, i, arr, ans):
		if i >= len(arr):
			if arr[:] not in ans:
				ans.append(arr[:])
			return
		for j in range(i, len(arr)):
			(arr[i], arr[j]) = (arr[j], arr[i])
			self.solve(i + 1, arr, ans)
			(arr[i], arr[j]) = (arr[j], arr[i])

	def uniquePerms(self, arr, n):
		result = []
		ans = set(permutations(arr))
		for i in ans:
			result.append(i)
		return sorted(result)
		ans = []
		self.solve(0, arr, ans)
		ans.sort()
		return ans


class Solution:

	def uniquePerms(self, arr, n):
		res = []
		arr.sort()
		self.dfs(arr, n, [], res)
		return res

	def dfs(self, arr, n, temp, res):
		if n == 0:
			res.append(temp)
			return
		for i in range(n):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			self.dfs(arr[:i] + arr[i + 1:], n - 1, temp + [arr[i]], res)


class Solution:

	def uniquePerms(self, arr, n):
		ans = []
		pos = 0
		self.per(arr, n, ans, pos)
		t = sorted(set(map(tuple, ans)))
		return t

	def per(self, arr, n, ans, pos):
		if pos >= n:
			ans.append(arr.copy())
		for i in range(pos, n):
			(arr[i], arr[pos]) = (arr[pos], arr[i])
			self.per(arr, n, ans, pos + 1)
			(arr[i], arr[pos]) = (arr[pos], arr[i])


import itertools

class Solution:

	def uniquePerms(self, arr, n):
		sets = set()
		for i in list(itertools.permutations(arr)):
			sets.add(tuple(i))
		return sorted(list(sets))


class Solution:

	def uniquePerms(self, arr, n):
		ans = []

		def fun(arr, idx):
			if idx == n - 1:
				ans.append(arr[:])
				return
			else:
				hash = []
				for i in range(idx, n):
					if arr[i] not in hash:
						hash.append(arr[i])
						(arr[i], arr[idx]) = (arr[idx], arr[i])
						fun(arr, idx + 1)
						(arr[i], arr[idx]) = (arr[idx], arr[i])
		fun(arr, 0)
		ans.sort()
		return ans


class Solution:

	def permutationHelper(self, i, arr, permutation):
		if i == len(arr) - 1:
			permutation.add(tuple(arr[:]))
		else:
			for j in range(i, len(arr)):
				(arr[i], arr[j]) = (arr[j], arr[i])
				self.permutationHelper(i + 1, arr, permutation)
				(arr[i], arr[j]) = (arr[j], arr[i])

	def uniquePerms(self, arr, n):
		result = set()
		self.permutationHelper(0, arr, result)
		perm = sorted(result)
		finalResult = [list(map(int, val)) for val in perm]
		return finalResult


class Solution:

	def uniquePerms(self, arr, n):

		def f(i, vis, n, arr, temp, ans):
			if i == n:
				ans += [temp]
				return
			for j in range(n):
				if not vis[j]:
					vis[j] = 1
					f(i + 1, vis, n, arr, temp + [arr[j]], ans)
					vis[j] = 0
		ans = []
		vis = [0] * n
		f(0, vis, n, sorted(arr), [], ans)
		ans.sort()
		res = [ans[0]]
		for i in range(1, len(ans)):
			if ans[i] != ans[i - 1]:
				res += [ans[i]]
		return res


class Solution:

	def uniquePerms(self, arr, n):

		def helper(pos):
			if pos >= len(arr):
				ans.add(tuple(arr))
			for i in range(pos, len(arr)):
				(arr[i], arr[pos]) = (arr[pos], arr[i])
				helper(pos + 1)
				(arr[i], arr[pos]) = (arr[pos], arr[i])
		ans = set()
		helper(0)
		return sorted(list(ans))


class Solution:

	def uniquePerms(self, arr, n):
		ans = []
		s = set()

		def hashkey(arr):
			s = ''
			for i in arr:
				s += str(i)
			return s

		def solve(arr, i, n, key):
			if i >= len(arr):
				ans.append(arr.copy())
				s.add(key)
				return
			for j in range(len(arr)):
				(arr[i], arr[j]) = (arr[j], arr[i])
				key = hashkey(arr)
				if key not in s:
					solve(arr, i + 1, n, key)
				(arr[i], arr[j]) = (arr[j], arr[i])
		key = hashkey(arr)
		solve(arr, 0, n, key)
		ans.sort()
		return ans


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		l = permutations(arr)
		l = list(l)
		p = list(set(l))
		return sorted(p)


class Solution:

	def permute(self, nums, cid, l):
		if len(nums) - 1 == cid:
			l.append(nums[:])
			return
		for i in range(cid, len(nums)):
			(nums[i], nums[cid]) = (nums[cid], nums[i])
			self.permute(nums, cid + 1, l)
			(nums[i], nums[cid]) = (nums[cid], nums[i])

	def uniquePerms(self, arr, n):
		arr.sort()
		l = []
		self.permute(arr, 0, l)
		s = {}
		b = []
		for i in l:
			d = str(i)
			d = d.replace('10', '99')
			s[d] = i
		for i in sorted(s):
			b.append(s[i])
		return b


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		result = []
		ans = set(permutations(arr))
		for i in ans:
			result.append(i)
		return sorted(result)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		b = list(permutations(arr))
		d = {}
		for i in b:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		a = list(d.keys())
		return sorted(a)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


class Solution:

	def uniquePerms(self, arr, n):
		nums = arr
		n = len(nums)
		ans = {}
		temp = []
		freq = [0 for i in range(n)]

		def check(ans, temp, freq, nums):
			if len(temp) == n:
				b = temp.copy()
				if tuple(b) not in ans:
					ans[tuple(b)] = 1
				return
			for i in range(n):
				if freq[i] == 0:
					freq[i] = 1
					temp.append(nums[i])
					check(ans, temp, freq, nums)
					temp.pop()
					freq[i] = 0
		m = check(ans, temp, freq, nums)
		m1 = ans.keys()
		return sorted(m1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


from collections import Counter

class Solution:

	def uniquePerms(self, arr, n):

		def helper(index, l):
			if index == n:
				ans.append(l.copy())
			for i in d:
				if d[i] > 0:
					d[i] -= 1
					l.append(i)
					helper(index + 1, l)
					l.pop()
					d[i] += 1
		n = len(arr)
		map = [0] * n
		d = Counter(arr)
		ans = []
		l = []
		helper(0, l)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


class Solution:

	def uniquePerms(self, arr, n):
		res = []
		perm = []
		count = {}
		for i in arr:
			if i in count:
				count[i] += 1
			else:
				count[i] = 1

		def dfs(len_perm):
			if len_perm == n:
				res.append(perm.copy())
				return
			for i in count:
				if count[i] > 0:
					perm.append(i)
					count[i] -= 1
					dfs(len_perm + 1)
					count[i] += 1
					perm.pop()
			return
		dfs(0)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


from collections import defaultdict

class Solution:

	def uniquePerms(self, nums, n):
		res = []
		hmap = defaultdict(int)
		for i in range(len(nums)):
			hmap[nums[i]] += 1

		def solve(perm):
			if len(perm) == len(nums):
				res.append(perm.copy())
				return
			for i in hmap:
				if hmap[i] > 0:
					hmap[i] -= 1
					perm.append(i)
					solve(perm)
					hmap[i] += 1
					perm.pop()
		solve([])
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


class Solution:

	def uniquePerms(self, arr, n):
		visited = [False for i in range(n)]
		ans = set()
		path = []

		def permute(i, n):
			if i == n:
				ans.add(tuple(path))
				return
			for j in range(n):
				if visited[j] == False:
					path.append(arr[j])
					visited[j] = True
					permute(i + 1, n)
					visited[j] = False
					path.pop()
		permute(0, n)
		ans = list(ans)
		ans.sort()
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		res = ob.uniquePerms(arr, n)
		for i in range(len(res)):
			for j in range(n):
				print(res[i][j], end=' ')
			print()


class Solution:

	def uniquePerms(self, nums, n):
		res = []
		nums.sort()
		self.dfs(nums, [], res)
		return res

	def dfs(self, nums, path, res):
		if not nums:
			res.append(path)
		for i in range(len(nums)):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			self.dfs(nums[:i] + nums[i + 1:], path + [nums[i]], res)


class Solution:

	def uniquePerms(self, arr, n):
		ans = []
		arr.sort()
		visited = [False] * n
		self.solver(arr, ans, [], visited)
		return ans

	def solver(self, arr, ans, ssf, visited):
		if len(ssf) == len(arr):
			ans.append(ssf[:])
			return
		for i in range(len(arr)):
			if i > 0 and arr[i] == arr[i - 1] and visited[i - 1]:
				continue
			if visited[i] == False:
				visited[i] = True
				self.solver(arr, ans, ssf + [arr[i]], visited)
				visited[i] = False


class Solution:

	def uniquePerms(self, nums, n):
		if len(nums) == 1:
			return [nums]
		ans = []
		seen = set([])
		for (ind, n) in enumerate(nums):
			if n in seen:
				continue
			seen.add(n)
			for j in self.uniquePerms(nums[:ind] + nums[ind + 1:], n):
				ans += [[n] + j]
		return sorted(ans)


class Solution:

	def hash(self, permutation):
		return ''.join((str(num) for num in permutation))

	def uniquePerms_rec(self, arr, n, uniques):
		if n == 1:
			return [arr]
		rec_permutations = self.uniquePerms_rec(arr[1:], n - 1, uniques)
		permutations = []
		for perm in rec_permutations:
			for i in range(n):
				new_perm = perm[:]
				new_perm.insert(i, arr[0])
				if self.hash(new_perm) not in uniques:
					permutations.append(new_perm)
					uniques.add(self.hash(new_perm))
		return sorted(permutations)

	def uniquePerms(self, arr, n):
		uniques = set()
		return self.uniquePerms_rec(arr, n, uniques)


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		perms = set()
		cur_perm = []
		visited = [False] * len(arr)

		def recur(n, arr, visited):
			nonlocal cur_perm
			if len(cur_perm) == n:
				perms.add(tuple(cur_perm[:]))
				return
			for i in range(n):
				if not visited[i]:
					visited[i] = True
					cur_perm.append(arr[i])
					recur(n, arr, visited)
					cur_perm.pop()
					visited[i] = False
		recur(n, arr, visited)
		return sorted(perms)


class Solution:

	def uniquePerms(self, arr, n):

		def rec(res, ans, dic, n):
			if len(ans) == n:
				res.append(ans.copy())
				return
			for elem in dic:
				if dic[elem] > 0:
					ans.append(elem)
					dic[elem] -= 1
					rec(res, ans, dic, n)
					dic[elem] += 1
					ans.pop()
		dic = {}
		res = []
		ans = []
		for item in arr:
			dic[item] = 1 + dic.get(item, 0)
		rec(res, ans, dic, n)
		return res


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		ans = list(set(permutations(arr)))
		ans.sort()
		return ans


class Solution:

	def uniquePerms(self, arr, n):

		def recur(i):
			nonlocal n
			if i == n - 1:
				return [arr.copy()]
			l = recur(i + 1)
			size = len(l)
			for x in range(size):
				t = l[x]
				for ind in range(i + 1, n):
					if t[ind] != t[i]:
						new = t.copy()
						(new[ind], new[i]) = (new[i], new[ind])
						l.append(new)
			return l
		res = sorted(recur(0))
		ans = []
		prev = []
		for i in res:
			if i != prev:
				ans.append(i)
				prev = i
		return ans


class Solution:

	def __init__(self):
		self.ans = {}

	def uniquePerms(self, arr, n):
		self.helper(0, arr)
		ans = self.ans.keys()
		return sorted(ans)

	def helper(self, i, arr):
		if i == len(arr) - 1:
			if tuple(arr) not in self.ans:
				self.ans[tuple(arr)] = 1
		for j in range(i, len(arr)):
			temp = arr.copy()
			(temp[i], temp[j]) = (temp[j], temp[i])
			self.helper(i + 1, temp)


class Solution:

	def uniquePerms(self, arr, n):
		result = []

		def solve(nums, i):
			if len(nums) <= i:
				result.append(list(nums))
				return
			look = set()
			for j in range(i, len(nums)):
				if nums[j] not in look:
					(nums[j], nums[i]) = (nums[i], nums[j])
					solve(nums, i + 1)
					(nums[j], nums[i]) = (nums[i], nums[j])
					look.add(nums[j])
		solve(arr, 0)
		result.sort()
		return result


class Solution:

	def uniquePerms(self, arr, n):
		ans = []
		arr.sort()

		def solve(arr, l):
			if len(arr) == 0:
				ans.append(l.copy())
			for i in range(len(arr)):
				if i > 0 and arr[i] == arr[i - 1]:
					continue
				else:
					l.append(arr.pop(i))
					solve(arr, l)
					arr.insert(i, l.pop())
		solve(arr, [])
		return ans


class Solution:

	def uniquePerms(self, arr, n):

		def dfs(path, used, res):
			used_at_node = set()
			if len(path) == n:
				res.append(path.copy())
				return
			for (idx, number) in enumerate(arr):
				if used[idx] == True:
					continue
				if number in used_at_node:
					continue
				path.append(number)
				used[idx] = True
				used_at_node.add(number)
				dfs(path, used, res)
				path.pop()
				used[idx] = False
		res = []
		dfs([], [False] * n, res)
		return sorted(res)


class Solution:

	def uniquePerms(self, nums, n):
		ans = []

		def helper(indx):
			if indx == len(nums):
				ans.append(nums[:])
				return
			visited = set()
			for i in range(indx, len(nums)):
				if nums[i] not in visited:
					(nums[indx], nums[i]) = (nums[i], nums[indx])
					helper(indx + 1)
					(nums[i], nums[indx]) = (nums[indx], nums[i])
					visited.add(nums[i])
		helper(0)
		ans.sort()
		return ans


from itertools import permutations as p

class Solution:

	def uniquePerms(self, arr, n):
		z = []
		ans = set(p(arr))
		for i in ans:
			z.append(i)
		return sorted(z)


class Solution:

	def uniquePerms(self, arr, n):
		m = [False for i in range(n)]
		ans = []
		arr.sort()

		def f(ds, ans, arr, m):
			if len(ds) == len(arr):
				ans.append(ds[:])
				return
			for i in range(len(arr)):
				if m[i]:
					continue
				if i > 0 and arr[i] == arr[i - 1] and (m[i - 1] == False):
					continue
				ds.append(arr[i])
				m[i] = True
				f(ds, ans, arr, m)
				del ds[-1]
				m[i] = False
		f([], ans, arr, m)
		return ans


class Solution:

	def uniquePerms(self, arr, n):
		res = set()
		Res = set()
		dict_ = {}
		self.solve(arr, res, 0, n)
		res = sorted(res)
		return res

	def solve(self, arr, res, start, end):
		if start == end:
			res.add(tuple(arr.copy()))
			return
		for i in range(start, end):
			(arr[i], arr[start]) = (arr[start], arr[i])
			self.solve(arr, res, start + 1, end)
			(arr[i], arr[start]) = (arr[start], arr[i])
		return


class Solution:

	def uniquePerms(self, arr, n):
		s = set()

		def helper(rem, a):
			if len(rem) == 0:
				x = a.copy()
				s.add(tuple(x))
			else:
				for i in range(len(rem)):
					a1 = a.copy()
					b1 = rem.copy()
					b1.pop(i)
					a1.append(rem[i])
					helper(b1, a1)
		helper(arr, [])
		s = list(s)
		s.sort()
		return list(s)


from itertools import permutations

class Solution:

	def uniquePerms(self, arr, n):
		final = []
		perm = set(permutations(arr))
		for ele in perm:
			final.append(ele)
		return sorted(final)


class Solution:

	def uniquePerms(self, arr, n):
		counts = [0] * 10
		for a in arr:
			counts[a - 1] += 1
		res = []
		per = []
		pos = 0
		self.solve(counts, per, res)
		return res

	def solve(self, counts, per, res):
		if sum(counts) == 0:
			res.append(per[:])
			return
		for i in range(10):
			if counts[i] > 0:
				per.append(i + 1)
				counts[i] -= 1
				self.solve(counts, per, res)
				per.pop()
				counts[i] += 1


from itertools import permutations
import heapq

class Solution:

	def uniquePerms(self, arr, n):
		(out, perm) = ([], [])
		count = {n: 0 for n in arr}
		for i in arr:
			count[i] += 1

		def dfs():
			if len(perm) == len(arr):
				out.append(perm.copy())
				return
			for n in count:
				if count[n] > 0:
					perm.append(n)
					count[n] -= 1
					dfs()
					perm.pop()
					count[n] += 1
		dfs()
		return out


from itertools import permutations

class Solution:

	def perm(self, a, start, end, level):
		global s
		if level == end:
			s.add(tuple([i for i in a]))
			return
		for i in range(start, end):
			(a[i], a[start]) = (a[start], a[i])
			self.perm(a, start + 1, end, level + 1)
			(a[i], a[start]) = (a[start], a[i])

	def uniquePerms(self, arr, n):
		global s
		s = set()
		self.perm(arr, 0, n, 0)
		s = sorted(list(s))
		return s


class Solution:

	def uniquePerms(self, arr, n):
		res = []
		self.permute(arr, 0, n, res)
		return sorted(list(set(res)))

	def permute(self, a, l, r, res):
		if l == r:
			res.append(tuple(a))
		else:
			for i in range(l, r):
				(a[l], a[i]) = (a[i], a[l])
				self.permute(arr, l + 1, r, res)
				(a[l], a[i]) = (a[i], a[l])


from itertools import permutations as perm

class Solution:

	def uniquePerms(self, arr, n):
		c = perm(arr)
		d = []
		for i in set(c):
			d.append(i)
		return sorted(d)


class Solution:

	def uniquePerms(self, arr, n):
		if n == 1:
			return [arr]
		arr.sort()
		ret = []
		for i in range(n):
			if i > 0 and arr[i - 1] == arr[i]:
				continue
			val = self.uniquePerms(arr[:i] + arr[i + 1:], n - 1)
			for v in val:
				ret.append([arr[i]] + v)
		return ret