90. Subsets II

#include <stdlib.h>
#include <string.h>

static int cmp(const void *a, const void *b) {
  int x = *(const int *)a, y = *(const int *)b;
  return (x > y) - (x < y);
}

static void backtrack(int *nums, int n, int idx, int *cur, int curSize,
                      int **result, int *returnSize, int *colSizes) {
  if (idx == n) {
    result[*returnSize] = malloc(curSize * sizeof(int));
    memcpy(result[*returnSize], cur, curSize * sizeof(int));
    colSizes[(*returnSize)++] = curSize;
    return;
  }

  cur[curSize] = nums[idx];
  backtrack(nums, n, idx + 1, cur, curSize + 1, result, returnSize, colSizes);

  int i = idx + 1;
  while (i < n && nums[idx] == nums[i])
    i++;

  backtrack(nums, n, i, cur, curSize, result, returnSize, colSizes);
}

int **subsetsWithDup(int *nums, int numsSize, int *returnSize,
                     int **returnColumnSizes) {
  int total = 1 << numsSize; // upper bound, reached only without duplicates
  int **result = malloc(total * sizeof(int *));
  *returnColumnSizes = malloc(total * sizeof(int));
  *returnSize = 0;
  qsort(nums, numsSize, sizeof(int), cmp);
  int cur[numsSize > 0 ? numsSize : 1];
  backtrack(nums, numsSize, 0, cur, 0, result, returnSize, *returnColumnSizes);
  return result;
}

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> subsetsWithDup(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> cur;
    sort(nums.begin(), nums.end());
    backtrack(nums, 0, cur, result);
    return result;
  }

  void backtrack(vector<int> &nums, int idx, vector<int> &cur,
                 vector<vector<int>> &result) {
    if (idx == nums.size()) {
      result.push_back(cur);
      return;
    }

    cur.push_back(nums[idx]);
    backtrack(nums, idx + 1, cur, result);
    cur.pop_back();

    int i = idx + 1;
    while (i < nums.size() && nums[idx] == nums[i])
      i++;

    backtrack(nums, i, cur, result);
  }
};

package backtracking

import "sort"

func subsetsWithDup(nums []int) [][]int {
    var result [][]int
    var cur []int
    sort.Ints(nums)

    var backtrack func(idx int)
    backtrack = func(idx int) {
        if idx == len(nums) {
            result = append(result, append([]int(nil), cur...))
            return
        }

        cur = append(cur, nums[idx])
        backtrack(idx + 1)
        cur = cur[:len(cur)-1]

        i := idx + 1
        for i < len(nums) && nums[idx] == nums[i] {
            i++
        }

        backtrack(i)
    }

    backtrack(0)
    return result
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int idx, List<Integer> cur, List<List<Integer>> result) {
        if (idx == nums.length) {
            result.add(new ArrayList<>(cur));
            return;
        }

        cur.add(nums[idx]);
        backtrack(nums, idx + 1, cur, result);
        cur.remove(cur.size() - 1);

        int i = idx + 1;
        while (i < nums.length && nums[idx] == nums[i]) {
            i++;
        }

        backtrack(nums, i, cur, result);
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  const result = [];
  const cur = [];
  nums.sort((a, b) => a - b);

  const backtrack = (idx) => {
    if (idx === nums.length) {
      result.push([...cur]);
      return;
    }

    cur.push(nums[idx]);
    backtrack(idx + 1);
    cur.pop();

    let i = idx + 1;
    while (i < nums.length && nums[idx] === nums[i]) i++;

    backtrack(i);
  };

  backtrack(0);
  return result;
};

from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        cur: List[int] = []
        nums.sort()

        def backtrack(idx: int) -> None:
            if idx == len(nums):
                result.append(cur[:])
                return

            cur.append(nums[idx])
            backtrack(idx + 1)
            cur.pop()

            i = idx + 1
            while i < len(nums) and nums[idx] == nums[i]:
                i += 1

            backtrack(i)

        backtrack(0)
        return result

impl Solution {
    pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut cur = Vec::with_capacity(nums.len());
        nums.sort_unstable();
        Self::backtrack(&nums, 0, &mut cur, &mut result);
        result
    }

    fn backtrack(nums: &[i32], idx: usize, cur: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if idx == nums.len() {
            result.push(cur.clone());
            return;
        }

        cur.push(nums[idx]);
        Self::backtrack(nums, idx + 1, cur, result);
        cur.pop();

        let mut i = idx + 1;
        while i < nums.len() && nums[idx] == nums[i] {
            i += 1;
        }

        Self::backtrack(nums, i, cur, result);
    }
}