1

Code is below

find the subarray which matches given sum

arr is given array, s is the sum

def getsub(arr,s): result = [] for x in range(len(arr)): result.append(arr[x]) while sum(result) > s: result.pop(0) if sum(result) == s: return result arr = [4, 1, 6, 5, 2, 3] s=5 getsub(arr,s)

I got only [4,1] only the first occurance

But actual output is [4,1] [5] [2,3]

Can i do it in o(n) time. I have done with (o(n3))TC by printing all the subarray and check the sum which is equal to s. which is not optimal

Improve this question
5
  • I'm not sure if it is doable in O(n) time since it can have multiple combinations, and the number of elements in the subarray seems to be varying Commented Sep 21, 2021 at 5:28
  • @ThePyGuy Agreed, if it was just 2 numbers each it would be easy in O(n), but with subarrays of any size, id assume its O(n!) or something like that Commented Sep 21, 2021 at 5:32
  • Feels like a DP problem... Commented Sep 21, 2021 at 5:56
  • We can achieve O(n) using Hashing or Slidding Window technique. For further details you can check my answer. Happy coding :) Commented Sep 21, 2021 at 6:26
  • @Maws You can check my answer below Commented Sep 21, 2021 at 7:12

4 Answers 4

Reset to default
2

There could be 2 possible approach for this.

  1. Slidding Window
  2. Hashing

Slidding Window:

# Function to find sublist having a given sum using hashing sliding window def find_sub_list_using_sliding_window(arr, expected_sum): # maintains the sum of the current window windowSum = 0 # maintain a window `[low, high-1]` [low, high] = [0, 0] # store pairs equivalent to `expected_sum` sum_list = [] # consider every sublist starting from `low` index for low in range(len(arr)): # if the current window's sum is less than the given sum, # then add elements to the current window from the right while windowSum < expected_sum and high < len(arr): windowSum += arr[high] high = high + 1 # if the current window's sum is equal to the given sum if windowSum == expected_sum: s_index = low e_index = high - 1 sum_list.append([arr[s_index], arr[e_index]] if s_index != e_index else [arr[s_index]]) # at this point, the current window's sum is more than the given sum. # remove the current element (leftmost element) from the window windowSum -= arr[low] return sum_list

The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.

Hashing:

# Function to find sublist having a given sum using hashing def find_sub_list_using_hashing(arr, expected_sum): # insert `(0, -1)` pair into the set to handle the case when # a sublist with the given sum starts from index 0 num_dict = {0: -1} # keep track of the sum of elements so far sum_so_far = 0 # store pairs equivalent to `expected_sum` sum_list = [] # traverse the given list for i in range(len(arr)): # update sum_so_far sum_so_far += arr[i] # if `sum_so_far - expected_sum` is seen before, # we have found the sublist with sum equal to `expected_sum` if (sum_so_far - expected_sum) in num_dict: s_index = num_dict.get(sum_so_far - expected_sum) + 1 sum_list.append([arr[s_index], arr[i]] if s_index != i else [arr[i]]) # insert (current sum, current index) pair into the dictionary num_dict[sum_so_far] = i return sum_list

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the input.

Driver Code:

if __name__ == '__main__': # a list of positive integers arr = [4, 1, 6, 5, 2, 3] expected_sum = 5 sum_list = find_sub_list_using_sliding_window(arr, expected_sum) print(f'Find Sub List Equivalen to a Given Sum Using Sliding Window: {sum_list}') sum_list = find_sub_list_using_hashing(arr, expected_sum) print(f'Find Sub List Equivalen to a Given Sum Using Hasing: {sum_list}')

Output:

Find Sub List Equivalen to a Given Sum Using Sliding Window: [[4, 1], [5], [2, 3]] Find Sub List Equivalen to a Given Sum Using Hasing: [[4, 1], [5], [2, 3]]
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

can you tell me how you become master in dynamic programming
I not master in DP, just know basics. :). Practice can make things easier for you. :)
1

This is the fastest structure I can think of:

def getsub(arr,s): results = [] result = [] for x in range(len(arr)): result.append(arr[x]) while sum(result) > s: result.pop(0) if sum(result) == s: results.append(result); result = [] return results 
arr = [4, 1, 6, 5, 2, 3] s=5 print(getsub(arr,s)) # [[4, 1], [5], [2, 3]]

It doesn't support nested or multiple combinations.

Improve this answer

5 Comments

We can achieve O(n) using Hashing or Slidding Window technique
@Sabil Learned some things from your ans.
if multiple compination, then it will not become subarray right?
@Sabil, can you post the answer
No, it doesn't support multiple combinations :(
1

Your algorithm running time is O(n) but if you want to better optimize the constants you can use this one which doesn't keep calling sum() over your sublist.

def summing(arr, n, sum_): current_sum = arr[0] start = 0 i = 1 while i <= n: while current_sum > sum_ and start < i-1: current_sum = current_sum - arr[start] start += 1 if current_sum == sum_: print ("Sum found at: {} and {}".format(start, i-1)) return 1 if i < n: current_sum = current_sum + arr[i] i += 1 print ("None found") return 0 arr = [15, 2, 4, 8] length = len(arr) sum_ = 6 summing(arr, length, sum_)

NOTE that these programs will fail if arrays indexes that can make this sum are not contiguous but this is the best i can think of as this problem is considered as NP complete if you don't require that sub array indexes to be contiguous in which elements can be any where in the array.

Improve this answer

Comments

0

JAVA Try this approach and construct a recursion tree to understand better

public class Combination_sum {

public static void main(String[] args) { int arr[]= {4, 1, 6, 5, 2, 3}; int target=5; List<Integer> ds=new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); findComb(0, target, ds, arr, ans); System.out.println(ans); } public static void findComb(int index,int target,List<Integer> ds,int arr[],List<List<Integer>> ans ){ if (index>arr.length-1) { if (target==0) { ans.add(new ArrayList<Integer>(ds)); } return; } if (arr[index]<=target) { ds.add(arr[index]); findComb(index, target-arr[index], ds, arr, ans); // take the number at that index ds.remove(ds.size()-1); } findComb(index+1, target, ds, arr, ans); // do not take the number at that index and move forward }

}

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.