# Simple python solution without extra space.

• class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]])
return res

if S[i] is same to S[i - 1], then it needn't to be added to all of the subset, just add it to the last l subsets which are created by adding S[i - 1]

• Excellent solution! "l" was the number of subsets created by the last s[j] where s[j] != s[j-1].

• Nice thoughts...
I met with something strange while implementing similar idea regarding to TLE

Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]]) # MAKE A CHANGE HERE : res[j].append(S[i]);res.append(res[j])
return res

append should work twice fast compared to '+' operation. But I got TLE after using append.
Any explanation?

• becasue you have changed res[j] which shouldn't be changed.

• damnnn nice one, the way you use l is really clever and fit into the loop to record the correct amount of subsets we need to process!

• @qqz003

One can find out its delicacy with few test cases.

• Really clever! Especially on length manipulation of results list

Here's the java version

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
results.add(new ArrayList<>());     // the [] set

Arrays.sort(nums);

int updateToLength = 0;

for (int i = 0; i < nums.length; i++) {
// new num, update all prev subsets
if (i == 0 || nums[i] != nums[i-1]) {
updateToLength = results.size();
}

List<List<Integer>> newSubsets = new ArrayList<>();
// if new num, append to all prev
// if dup, only append to subsets created by this dup num
// so increase in digits 14 => 144, 1444
for (int s = results.size() - updateToLength; s < results.size(); s++) {
List<Integer> subset = results.get(s);
List<Integer> appendSubset = new ArrayList<>(subset);
}
}
return results;
}

• Is the time complexity O(2^N)?

• How smart you are!!!

• Brilliant treatment on using the right items of old result to generate new items! This is really a clever example to show the ideas of backtracking! Thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.