What should be thinking process about solving this question.

Question

1.00/5 (1 vote)

See more:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7]

  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2]

  [2,3,3],
  [3,5]
]

Given these problem, i need help on:
1) What should be my approach to solve these type of questions.
2) In which direction should i think or on what basis should i start to think for solving these questions.

Thanks in advance.

PS:i don't need the solution, but i can't think of any starting point.

What I have tried:

i tried linear way of thinking, but it is not sufficient.

Posted 21-Nov-19 23:01pm

Jitesh Gala

Updated 22-Nov-19 1:19am

v2

Add a Solution

Comments

Richard MacCutchan 22-Nov-19 5:14am

I would suggest taking each number in turn and using it and any of the other values to see whether they add up to the target. Given that you can use the same numbers more than once it is a potentially long running process. One extra step you could try is to divide the target by the current number to see how many times it can fit. That would then give another target value to look for. For example, dividing 8 by 2 gives an immediate answer in the above sample.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Pete O'Hanlon · Answer 1 · 2019-11-22T01:21:00

This is a puzzler because you have been given incomplete information. The first step I would do, if I were you, would be to identify the missing pieces. For instance, the requirement says you are given a number of candidates with values; do those values have to be greater than zero? If they can only be greater than zero, you could perform a first pass optimisation of your problem by removing those entries that are greater than your target because there is no possible combination you could apply that could use those values.

In other words, before you attempt to solve the problem, make sure that you know what ALL of the problem is. Once you do that, your next step would be to stop thinking about how to write a program to do this. Step back and think how you would do it yourself. Don't worry about things such as algorithmic complexity or programming structures; just write down some examples and use pen and paper to try this task.

(A quick hint, if you have 1 in your candidate values then you can optimise your problem by saying that your first solution would be to use 1, a total number of times).

OriginalGriff · Answer 2 · 2019-11-21T23:36:00

Start by thinking about how you would do it manually - get a pen and paper and generate some examples, and try it. When you're sure you can do it for yourself, write down how to do it as a set of instructions, as a set of simple steps.

Then generate some new sets of numbers, and try following the instructions exactly and blindly. Did it work? If not, go back and improve the instructions. Try again.
When the instructions work, you have an algorithm and probably something reasonably close to pseudocode.
You can now start thinking about implementing that as as a computer program - teh instructions gets modified to produce actual pseudocode, and you can start implementing and testing that.

What you will come up with may not be the cleverest way, the fastest way - but you know it should work, and you can work on improvements once you test it and see if it's "quick enough" for the task.

This isn't a "solution" to this specific problem - but you didn't ask for one, and we probably wouldn't have given you one if you did - it's the basis of a generic method of thinking about problems and their solutions.

Patrice T · Answer 3 · 2019-11-22T00:46:00

Quote:
i tried linear way of thinking, but it is not sufficient.

What is 'linear way' ?

When you have no known efficient algorithm for a problem, you have to fallback to brute force search.
Brute force is trying all possible combination to get all answers.
Solving the problem by hand is a good way to get a first algorithm.
Brute-force attack - Wikipedia[^]

What should be thinking process about solving this question.

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0