FB Phone - Tuple Combination Sum


  • 0
    S

    Q: Write a function that list any 3 elements that sum to zero, from an array of integers.

    Notes:

    1. We need all unique solutions. (-5, -5, 10) is same as (10, -5, -5)
    2. The same element can be used multiple times.

    Example
    Input: [-5, 1, 10, 2, 3] // array of integers
    Output: [(-5, -5, 10), (-5, 2, 3)] // array of tuples


  • 0
    S

    I know this is similar to this problem - https://leetcode.com/problems/combination-sum/#/description. But the challenging thing is the array can contain negative elements. Any idea how we can solve this.


  • 0
    S
    1. also similar to 3 sum

    2. for backtrace
      Helper(List<List<int>> res, List<int> temp, int[] arr, int index, int sum, int count){
      if(index>=arr.Length)
      return;
      if(count==0){
      if(sum==0) // meet condition
      res.Add(new List<int>(temp));
      return;
      }

      Helper(.....index+1,...)// do nothing. go to next index, choose 0 time
      for(int i=1;i<=count;i++){// choose current item, choose 1 time, choose 2 time, choose 3 time
      temp.add(arr[index]);
      sum+=arr[index];
      Helper(....index+1,sum,count-i);
      }

      //remove all arr[index] from temp.
      for(int i=1;i<=count;i++){
      temp.remove(arr[index]);
      }
      }


  • 0
    S

    @skong03 Thanks for your code. I tried to solve this similar to 3sum. I copied each element in the array thrice (since we are looking for tuples) and built the new expanded input array. Then sorted the elements to skip the duplicate elements.


  • 6
    S
    
    def threesumzero(a):
        """
        Find triplets that sum to zero
        :param a: an array of integers to analyze
        :return: return unique triplets out of input array that sum to zero, an item in triplet may repeat at most twice
        """
        result = set()  # set to eliminate deuplicates!
        a.sort() # sort it
        n = len(a) # number of items in a
        for x in a: # for each element in a, see if its part of some triplet
            target_sum = 0 - x # x and other two items must sum to 0, so other two must sum to -x
            i = 0 # from beginning
            j = n - 1 # from end
            while i < j:
                if a[i] + a[j] == target_sum: # we found triplet
                    result.add( tuple( sorted( [x, a[i], a[j] ] ) ) ) # sort it (for uniqueness) and convert it to tuple as its immutable
                    i += 1
                    j -= 1
                elif a[i] + a[j] > target_sum:
                    j -= 1
                else: # a[i] + a[j] < target_sum
                    i += 1
    
        return result

  • 0
    V
    public class Solution11 {
    public Solution11() {
        super();
    }
    static Set<List> set = new HashSet<List>();
    public static void main(String[] args){
        int[] arr = {-5,1,10,2,3};
        for(int i=0;i<arr.length;i++){
            findSet(arr,i);
    }   
        System.out.println(set.toString());
    }
    
    public static void findSet(int[] arr, int i){
        for(int j=0;j<arr.length;j++){
            List<Integer> list = new ArrayList<Integer>();
            list.add(arr[i]);
            list.add(arr[j]);
            int output = findSet2(arr,i,j,list, arr[i]+arr[j]);
            if(output != 0){
                list.add(output);
                Collections.sort(list);
                set.add(list);
            }
        }
    }
    
     public static int findSet2(int[] arr, int i, int j, List<Integer> list,int sum){
        return (j == arr.length) ? 0 : ((sum + arr[j] == 0) ? arr[j] : findSet2(arr,i,j+1,list,sum));
     }
    }

  • 0
    R

    Simple but slow Python solution ( O(N^3))

    def find_triplets(a):
        solutions = set()
        if len(a) < 3:
            return 0
        for x in range(len(a)-2):
            for y in range(x, len(a)-1):
                for z in range(y, len(a)):
                    if a[x] + a[y] + a[z] == 0:
                        solutions.add((a[x], a[y], a[z]))
        return list(solutions)
    
    print(find_triplets([-5, 1, 10, 2, 3]))
    

  • 1

    Assume input array doesn't have duplicate number. If it has, remove first.

        public static void main(String[] args) {
            int[] nums = new int[]{-5, 1, 10, 2, 3, 7, 8, -11, 11, -6};
            System.out.println(tupleSum(nums));
        }
        private static List<List<Integer>> tupleSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                return res;
            }
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 2; i++) {
                int l = i, r = nums.length - 1;
                while (l <= r) {
                    if (nums[i] + nums[l] + nums[r] > 0) {
                        r--;
                    } else if (nums[i] + nums[l] + nums[r] < 0) {
                        l++;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        l++;
                        r--;
                    }
                }
            }
            return res;
        }
    

  • 1
    Y

    This question is very similar to the combination sum. just do not need to sort and return when the number of the current list reaches 3.

    class Solution {
     public:
      void helper(const vector<int>& curr_list, int target,
                  const vector<int>& candidates, int start_index,
                  vector<vector<int>>* res) {
        if (curr_list.size() == 3) {
          if (target == 0) {
            res->push_back(curr_list);
          }
          return;
        }
    
        for (int i = start_index; i < candidates.size(); i++) {
          int diff = target - candidates[i];
          auto new_vec = curr_list;
          new_vec.push_back(candidates[i]);
          helper(new_vec, diff, candidates, i, res);
        }
      }
    
      vector<vector<int>> combinationSum(vector<int>& candidates) {
        vector<vector<int>> res;
        helper(vector<int>(), 0, candidates, 0, &res);
        return res;
      }
    };
    

Log in to reply
 

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